Сортировка вставками ( insertion sort)
В данной сортировке мы вставляем каждый новый элемент на то место, чтобы массив был отсортирован. К примеру, есть у нас массив (4) (7) (1) (0) (5) и мы его хотим отсортировать по возрастанию. Создаём новый пустой массив такого же размера и помещаем первый элемент. Далее каждый следующий положим в нужное место:
(4)
(4) (7)
(1) (4) (7)
(0) (1) (4) (7)
(0) (1) (4) (5) (7)
В какое именно место класть, можно понять на примере. У нас есть (0) (1) (4) (7) и надо положить (5). Мы будем проверять (0) > (5) ? нет. И т.д. пока не дойдём до (7) > (5) ? да. Ну тогда ставим перед семёркой. Это был упрощённый пример для понимания принципа.
Ниже код с более совершенным алгоритмом, где левая часть массива будет отсортированной, а из правой части массива мы будем вставлять элементы в левую, таким образом сортируя весь массив:
void insertionsort(int a[], int size) {
int buf; // то что мы будем вставлять
// цикл прохода по исходному массиву
for (int i=1, j; i<size; i++) {
buf= a[i]; // берём первый левый элемент из неотсортированной части массива
// поиск места куда вставить и сдвиг неотсортированных элементов вправо (по циклу проходимся справа налево)
for (j= i-1; j>=0 && a[j]>buf; j--) a[j+1]= a[j];
a[j+1]= buf; // вставка в нужное место
}
}
Сортировка Шелла
Это некая модификация сортировки простыми вставками. Алгоритм достаточно сложный, поэтому комментировать и копаться я в нём не буду, это просто для ознакомления, что такой алгоритм вообще есть, и использования. Ниже весь алгоритм:
|
|
|
// вспомогательная функция
int increment(int inc[], int size) {
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s= -1;
do {
if (++s % 2) inc[s]= 8*p1 - 6*p2 + 1;
else {
inc[s]= 9*p1 - 9*p3 + 1; p2 *= 2; p3 *= 2;
}
p1*=2;
}
while(3*inc[s] < size);
return s>0 ? --s : 0;
}
// сама сортировка
void shellsort(int a[], int size) {
int inc, i, j, seq[40];
int s;
s= increment(seq, size);
while (s>=0) {
inc= seq[s--];
for (i=inc; i<size; i++) {
int temp= a[i];
for (j=i; (j>=inc) && (temp < a[j-inc]); j-=inc) {
a[j]= a[j-inc];
}
a[j]= temp;
}
}
}
Пирамидальная сортировка
Тоже малоизвестный и сложный для понимания алгоритм, поэтому я просто приведу рабочий и немного отредактированный код. При желании его можно разобрать.
// вспомогательная функция
void downHeap(int a[], int k, int n) {
int new_elem;
int child;
new_elem= a[k];
while(k <= n/2) {
child= 2*k;
if (child<n && a[child]<a[child+1]) child++;
if (new_elem >= a[child]) break;
a[k] = a[child];
k = child;
}
a[k] = new_elem;
}
// сама сортировка
void heapSort(int a[], int size) {
int i; int temp;
for(i= size/2 - 1; i>=0; i--) downHeap(a, i, size-1);
for(i= size-1; i>0; i--) {
temp= a[i]; a[i]= a[0]; a[0]= temp;
downHeap(a, 0, i-1);
}
}
Этот алгоритм уже быстрее рассмотренных ранее. Если у "типовых" алгоритмов скорость была O(n*n), то тут уже O(n*log(n))
Сортировка слиянием ( merge sort)
|
|
|
Ещё один сравнительно быстрый и рекурсивный алгоритм сортировки наряду с быстрой сортировкой, которую мы выдали ещё в 1-м разделе (или также quick sort, сортировка Хоара)
Сортировка слияния похожа на быструю сортировку. Здесь массив делится на две примерно равные половины, каждая половина сортируется этой же функцией (происходит рекурсия), а потом отсортированные массивы соединяются.
Если сравнивать с быстрой сортировкой, то там тоже происходит рекурсивное деление, но принцип сортировки другой и больше похож на пузырьковый. Только в первую очередь происходят перестановки элементов на наибольшем возможном расстоянии.
Что у быстрой сортировки, то и у сортировки слиянием- скорость алгоритма O(n*log(n)), как и у пирамидальной.
Теперь сам код сортировки слиянием- тут представлен метод нисходящего слияния.
void mergesort(int a[], int l, int r) {
if (l == r) return;
int mid = (l+r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
int i = l;
int j = mid + 1;
int *tmp = new int [r];
for (int step = 0; step < r - l + 1; step++) {
if ((j > r) || ((i <= mid) && (a[i] < a[j]))) { tmp[step] = a[i]; i++; }
else { tmp[step] = a[j]; j++; }
}
for (int step = 0; step < r - l + 1; step++) a[l + step] = tmp[step];
}
Используется сортировка массива из 11 элементов так: mergeSort(mass,0,10); т.е. указывается левый и правый элемент. Это было нужно для рекурсии. Можно сделать перегрузку чтобы можно было указывать как обычно- добавить ниже ещё 1 доп.функцию:
|
|
|
void mergesort(int a[], int size) {
mergesort(a,0,size-1);
}
И теперь можно использовать как обычно: mergesort(mass,11);
Ниже другой код сортировки слиянием, он организован без рекурсии. Этот метод называется методом восходящего слияния.
void mergesort(int a[], int size) {
int step = 1; int *temp= new int [size];
while (step<size) {
int index= 0; int l= 0; int m= l+step; int r= l+step*2;
do {
m= m<size ? m : size;
r= r<size ? r : size;
int i1= l, i2= m;
for (; i1 < m && i2 < r; ) {
if (a[i1]<a[i2]) temp[index++]= a[i1++];
else temp[index++]= a[i2++];
}
while (i1 < m) temp[index++]= a[i1++];
while (i2 < r) temp[index++]= a[i2++];
l+= step*2; m+= step*2; r+= step*2;
} while (l<size);
for (int i = 0; i < size; i++) a[i]= temp[i];
step*= 2;
}
}
Дата добавления: 2018-09-22; просмотров: 308; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!