第八单元 排序算法

8.1 常用排序算法

(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[i]<w[j];} // 自定义比较规则
……
sort(a, a+n, cmp);

cmp 要讲清 a[i]和 a[j]的比较方法。对于上面的代码，就是“如果 w[i]<w[j]，那么 a[i]就排在 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(n^2)时间）对排序的影响。

(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[i]=a[i];
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[i]<temp[j])
a[k]=temp[i++];
else
a[k]=temp[j--];
}

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