常用排序算法

(1) 使用STL算法!

平均时间：O(nlogn) 头文件：<algorithm>

① 调用方法：sort(第一项的地址, 最后一项的地址+1);

如sort(&a[0],&a[n]);或sort(a,a+n); 注意，STL的区间是左闭右开区间。

② 自定义规则的排序：有时排序的条件不止一个，或不方便对原数据进行排序，就需要自定义比较规则。

这时需要建立一个函数，把“小于”解释明白。例如：

bool cmp(const int &i, const int &j) {return w<w[j];}    …… sort(a, a+n, cmp);

// 自定义比较规则

cmp要讲清a和a[j]的比较方法。对于上面的代码，就是“如果w<w[j]，那么a就排在a[j] 的前面”。

(2) 快速排序!

平均时间：O(nlogn)

快速排序俗称“快排”，是基于比较的排序算法中最快的一种算法。

void quicksort(int *a, int start, int end) {   int low=start, high=end;   int temp, check=a[start];     // 划分：把比check小的数据放到它的左边，把比check大的数放到它的右边。   do   {   while (a[high]>=check&&low<high) high--;  // 注意，不要写成“low<=high”！   if (a[high]<check)    temp=a[high], a[high]=a[low], a[low]=temp;    while (a[low]<=check&&low<high) low++;  // 注意，不要写成“low<=high”！   if (a[low]>check)    temp=a[high], a[high]=a[low], a[low]=temp; } while (low!=high);    a[low]=check;  low--,high++; // 递归：对已经划分好的两部分分别进行快速排序 if (low>start) quicksort(a, start, low);

if (high<end) quicksort(a, high, end);

}

快速排序的版本很多，上面只是众多版本中的一种。

快速排序的三个优化方法：

1. 规模很小时（如end－start＜10），使用插入排序代替快速排序。

2. 使用栈模拟递归。

3. 极端数据（如比较有序的数组）会使快速排序变慢，甚至退化为冒泡排序。可以采用“三者取中法”

来解决这个问题：令check等于a[start]、a[end]、a[(start+end)/2]中的中间值。

第三种方法可以消除坏数据（基本有序的数据，它可以使快速排序退化为O(n2)时间）对排序的影响。

(3) 归并排序

时间复杂度：O(nlogn) 注意：

1. 其他排序算法的空间复杂度是O(1)，而归并排序的空间复杂度很大，为O(n)。

2. 下面的end是“末尾索引＋1”，即数列末尾要留一个空位。

int temp[N];  void mergesort(int *a, int start, int end) {  if (start+1>=end) return; // 划分阶段、递归 int mid = start+(end-start)/2;  mergesort(a, start, mid);  mergesort(a, mid, end); // 将mid两侧的两个有序表合并为一个有序表。 int p=start,q=mid,r=start;  while (p<mid || q<end)   if (q>=end || (p<mid && a[p]<=a[q]))    temp[r++]=a[p++];   else    temp[r++]=a[q++]; for (p=start;p<end;p++) a[p]=temp[p]; }

在(end-start)不太大时，可以用插入排序代替归并排序。

归并排序还有另一种写法：开始复制的时候，把第二个子数组中元素的顺序颠倒了一下。

int temp[N];       // “临时安置点” void mergesort(int *a, int start, int end) {  if (start==end) return; int mid = start+(end-start)/2;  mergesort(a, start, mid);  mergesort(a, mid, end);

// 合并 for (int i=mid; i>=start; i--) temp=a;  for (int j=1;j<=end-mid;j++) temp[end-j+1]=a[j+mid];   for (int i=start,j=end,k=start; k<=end; k++)   if (temp<temp[j])    a[k]=temp[i++];   else    a[k]=temp[j--]; }

在(end-start)不太大时，也可以用插入排序代替归并排序。