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

Август 30th, 2011 § 0 comments

Универсальный  алгоритм для сортировки, так же называется 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);
 }
}

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Смотреть фильмы онлайн