Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
- Bu sahifa navigatsiya:
- Листинг 2.10. Сортировка подсчетом
|
2.2.5. С
ОРТИРОВКА ПОДСЧЕТОМ Все ранее рассмотренные методы обеспечивали выполнение принципа сортировки in situ – на том же месте. Однако при отсутствии ограничения на используемую память можно использовать в процессе сортировки дополни- тельные массивы. В частности, можно переписывать элементы из исходного неотсортированного массива в результирующий массив сразу в нужном по- рядке. Тогда число наиболее трудоемких операций – пересылок элементов – будет ровно N. Разумеется, для определения номера элемента в новом масси- ве придется сделать какое-то количество сравнений. В качестве примера возьмем очень простую сортировку методом под- счета. Ее идея заключается в том очевидном факте, что i-й ключ в упорядо- ченном массиве превышает ровно i-1 остальных ключей, если никакие два ключа не равны. Таким образом, идея состоит в том, чтобы сравнить попарно все ключи и для каждого из них подсчитать количество ключей с меньшим значением. Для подсчетов числа ключей, меньших данного, используется вспомогательный массив счетчиков, значения которого служат для пересыл- ки элементов из исходного массива в новый. Для минимального элемента исходного массива значение соответствующего элемента массива счетчиков равно нулю. Сортировка подсчетом является устойчивой. В листинге 2.10 приведен алгоритм сортировки методом подсчета. Листинг 2.10. Сортировка подсчетом public void SortMove(int[] a) { int N = a.Length; int[] cnt = new int[N]; // массив счетчиков int[] b = new int[N]; // отсортированный массив // инициализация массива счетчиков for (int i = 0; i < N; i++) cnt[i]=0; // сравнение элементов и заполнение массива счетчи- ков for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) 6 / 23 30 if (a[i] > a[j]) ++cnt[i]; else ++cnt[j]; // пересылка элементов в новый массив for (int i=0; i for (int i = 0; i < N; i++) a[i] = b[i]; } Число сравнений в сортировке подсчетом C~N2, число пересылок (из исходного массива в новый) M=N. Поскольку операции пересылки являются более затратными по времени, чем сравнения, то скорость роста данного ал- горитма близка к линейной, т.е. O(N). Алгоритм дает правильный результат независимо от числа равных ключей. Download 1.85 Mb. Do'stlaringiz bilan baham: 
|