Методы сортировки

Сортировка методом прямого

включения

	void insertion_sort()
	{int i, j, x;
1	for(i =2; i <=n; i ++)
2	{ x:=a[i];a[0]=x; j=I;
3	while (x<a[j-1])
4	{ a[j]=a[j-1]; j--; }
5	a[j]=x;
	}
	} //end insertion_sort

Сортировка с помощью прямого

обмена («пузырьковая»)

void Bubble_sort()

{int i, j, x;

1for(i =2; i <=n; i ++)

2	for(j=n;j<=i;j--)
3	if (a[j-1]>a[j])
4	{ x=a[j]; a[j]=a[j-1];a[j-1]=x;}
	} //end Bubble_sort

Сортировка с помощью прямого выбора

void selection_sort()

1 {int i, j, k, x;

2for(i =1; i <n; i ++)

3{ k= i; x=a[i]

4	for(j=i+1;j<=n;j++)
5	if (a[j<x) {k=j; x=a[k];}
6	a[k]=a[i]; a[i]=x;

7}

} //end selection_sort

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

44 52 12 22 94 42 55 13 25 18 89 i=1, j=11 ---- i=1, j=10 ---- i=2, j=9 18 52 12 22 94 42 55 13 25 44 89 i=2, j=9 ---- i=2, j=9 ---- i=3, j=8 18 25 12 22 94 42 55 13 52 44 89 I=3, j=8 ---- i=5, j=8 ---- i=6, j=8 18 25 12 22 13 42 55 94 52 44 89 i=6, j=8 ---- i=6, j=5 –-- i=6, j=5

Элементы a1, a2, …ai-1 имеют значения <= x Элементы ai, ai+1, …an n имеют значения > x

Улучшенные методы сортировки: Быстрая сортировка

18 25 12 22 13 42 55 94 52 44 89 i=7, j=8

Разбиваем массив на две части (1,6) --- (7,11)

Повторяем процесс для каждой части по отдельности

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

void Quick_sort(int L, int R) {int i,j, x, y;

i =L; j=R; x=a[(L+R)/2]; do

while (a[i]<x) I++; while (a[j]<x) j--;; if(i <=j)

{ y=a[i]; a[i]=a[j]; a[j]=y; i ++;j--} while (i<=j)

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

if(L<j) Quick_sort(L, j); if(i<R) Quick_sort(i, R); } //end Quick_sort

Вызов функции Quick_sort(1,n);

n – количество элементов массива