Общий алгоритм

Пирамидальная сортировка

44 55 12 42 94 18 06 67 исходный массив 44 55 12 42 67 18 06 |94 94 < -> 67 44 55 12 42 06 18 |67 94 67 < -> 06 44 18 12 42 06 |55 67 94 55 < -> 18 06 18 12 42 |44 55 67 94 44 < -> 06 06 18 12 |42 44 55 67 94 42 < -> 42 06 12 |18 42 44 55 67 94 18 < -> 12 06 |12 18 42 44 55 67 94 12 < -> 12

характеристическое свойство: a[i] > = a[2i+1] и a[i] > = a[2i+2].

Фаза 1 сортировки: построение пирамиды

44 55 12 42 // 94 18 06 67 Справа - часть массива, 44 55 12 // 67 94 18 06 42 удовлетворяющая свойству44 55 // 18 67 94 12 06 42 пирамиды, остальные44 // 94 18 67 55 12 06 42 элементы добавляются один // 94 67 18 44 55 12 06 42 за другим, справа налево

Фаза 2: собственно сортировка

94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы 67 55 44 06 42 18 12 // 94 сортировки пирамиды 55 42 44 06 12 18 // 67 94 во внутреннем 44 42 18 06 12 // 55 67 94 представлении 42 12 18 06 // 44 55 67 94 18 12 06 // 42 44 55 67 94 12 06 // 18 42 44 55 67 94 06 // 12 18 42 44 55 67 94

Быстрая сортировка

Общий алгоритм

quickSort (массив a, верхняя граница N) {Выбрать опорный элемент p - середину массиваРазделить массив по этому элементуЕсли подмассив слева от p содержит более одного элемента, вызвать quickSort для него. Если подмассив справа от p содержит более одного элемента, вызвать quickSort для него. }

void quickSortR(int* a, long N) {// На входе - массив a[], a[N] - его последний элемент. long i = 0, j = N; // поставить указатели на исходные места int temp, p; p = a[ N> > 1 ]; // центральный элемент//---------------------------------- процедура разделения do { while (a[i] < p) i++; while (a[j] > p) j--; if (i < = j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i< =j); // рекурсивные вызовы, если есть, что сортировать if (j > 0) quickSortR(a, j); if (N > i) quickSortR(a+i, N-i); }

4. Сортировка слиянием

a - сортируемый массив, его левая граница lb, правая граница ub void mergeSort(int a[], long lb, long ub) { long split; // индекс, по которому делим массив if (lb < ub) { // если есть более 1 элемента split = (lb + ub)/2; mergeSort(a, lb, ub); // сортировать левую половину mergeSort(a, split+1, last); // сортировать правую половину merge(a, lb, split, ub); // слить результаты в общий массив }}

merge(упорядоченные последовательности A, B, буфер C) { пока A и B непусты { cравнить первые элементы A и B переместить наименьший в буфер }если в одной из последовательностей еще есть элементыдописать их в конец буфера, сохраняя имеющийся порядок}

Пример работы на последовательностях 2 3 6 7 и 1 4 5

<== предыдущая лекция	\|	следующая лекция ==>
Принципы педагогического проектирования	\|	Сортировка с помощью выделения (прямого выбора)

Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2025 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал