Универсальный алгоритм для сортировки, так же называется qsort или quicksort. был разработан в 1960 году Чарльзом Хоаром. Сортировка в среднем за O(n*log n), но в худшем случае может деградировать до O(n^2). Данный вид сортировки, является не устойчивым. Ниже код на С++
void swap(int& a,int& b) { int t = a; a=b; b=t; } int partition(int s[],int l,int h) { int i; int p; int firsthigh; p=h; firsthigh=l; for(i=l;i<h;i++) { if(s[i]<s[p]) { swap(s[i],s[firsthigh]); firsthigh++; } } swap(s[p],s[firsthigh]); return firsthigh; } void quicksort(int s[],int l,int h) { int p; if((h-l)>0) { p=partition(s,l,h); quicksort(s,l,p-1); quicksort(s,p+1,h); } }
Оставить комментарий