快速排序、归并排序、堆排序与希尔排序
该时期的算法可以达到O(N·logN)的时间复杂度，几乎已经是速度的极限了。快排和归并排序还使用了分治的思想，理解起来并不轻松。
快速排序
选择某元素作为哨兵并划分数组，使得大于和小于它的元素们分别集中在它的左右两侧，那么对它的左右两侧分别应用以上策略，直至排序结束。
该技术重点在于“划分”的过程。基本策略如下[注2]：
- 哨兵元素交换至队尾
- 定义一个“小于等于区间”（初始为空），当被处理元素小于等于哨兵元素时，与该区间右侧元素交换，并纳入到该区间内。(快排是不稳定算法，所以等于哨兵元素时怎么处理都无所谓)
- 哨兵元素与小于等于区间右侧元素交换。
CODE
int* quickSort(int* A, int n) {
//整体是一个递归，指定递归的结束条件
if(n<=1)
return A;
//在[0,n-1]间随机选择一个位置来交换至队尾
int pos=rand()%n;
swap(A[pos],A[n-1]);
//小于等于区间的右边界，初始为-1
int k=-1;
for(int i=0;i<n-1;++i){
//有没有等于无所谓
if(A[i]<A[n-1]){
//交换区间右侧元素，并扩展区间
swap(A[k+1],A[i]);
k++;
}
}
//交换区间右侧元素，换回哨兵
swap(A[k+1],A[n-1]);
//分治子区间
quickSort(A,k+1);
quickSort(A+k+2,n-k-2);
return A;
}
归并排序
归并排序基本上是分治和递归的最经典案例了。因为合并两个有序数组是比较容易的，所以如果对数组A进行排序，只需要排好A的前后两个子序列，然后合并这两个子序列即可。对A的子序列进行排序，用的同样是以上方法，这就是典型的“方法调用自身”的实现。
规划上，排序是从上而下的切分；实现上，排序是从下而上的整合。
CODE
//数组A的前m个数和后n个数都是有序的，合并它们
void merge(int* A,int m,int n){
//开辟数组用于合并两个子序列的临时空间
int* t=new int[m+n];
int pos=0;
//分别对序列计数
int i=0,j=0;
//两个子序列的首地址
int* p=A,*q=A+m;
//循环直至其中一个子序列遍历完成
while(i<m && j<n){
if(p[i]<q[j]){
t[pos++]=p[i++];
}else{
t[pos++]=q[j++];
}
}
//处理未遍历完的子序列
while(i<m)
t[pos++]=p[i++];
while(j<n)
t[pos++]=q[j++];
//誊写回去原来的数组
for(int i=0;i<m+n;++i)
A[i]=t[i];
delete[] t;
}
int* mergeSort(int* A, int n) {
if(n>1){
mergeSort(A,n/2);
mergeSort(A+n/2,n-n/2);
merge(A,n/2,n-n/2);
}
return A;
}
注意
- 在函数中反复申请和释放堆内存会产生负担，建议使用全局数组来替代
- 虽然有其他方法可以避免申请O(N)的内存，但是会产生额外时间花销
堆排序
堆排序借鉴了堆的结构，其核心算法在于大根堆的调整。
大根堆：所有根节点的值大于等于其左右子结点的值。
步骤：
- 首先建立大根堆，方式是从底到顶的逐元素调整；
- 每次交换堆顶（即最大值）与末尾元素，缩减堆的规模，并从堆顶做调整。循环此步骤至堆的规模为1。
大根堆的调整：待处理结点如果不是其左右孩子的最大值，则需要与最大值项进行交换，并沿着被交换项一路向下，直至不需交换或至叶节点为止。
CODE
int* heapSort(int* A, int n) {
// 建立大根堆：从最后一个非叶节点开始。当然即使是叶节点也没关系
for(int i=n/2-1;i>=0;--i)
adjust(A,i,n);
while(n>=1){
//交换堆顶元素至队尾
swap(A[0],A[n-1]);
//缩小堆的规模，从堆顶元素调整堆
adjust(A,0,n-1);
n--;
}
return A;
}
//调整以数组A构建的大根堆的第i个结点
void adjust(int* A,int i,int n){
//最大项暂定为i
int max=i;
//如果左结点存在且大于当前最大项
if(2*i+1<n && A[2*i+1]>A[i]){
max=2*i+1;
}
//如果右结点存在且大于当前最大项
if(2*i+2<n && A[2*i+2]>A[max]){
max=2*i+2;
}
//如果需要交换，则沿着被交换项进行递归调用
if(max!=i){
swap(A[max],A[i]);
adjust(A,max,n);
}
}
注意
- 堆排序的主要思想在于每一步的调整后，都可以维持大根堆的结构，下一步的调整就可以依靠大根堆的结构在O(logN)的时间内完成。
希尔排序
希尔排序是从插入排序进化来的算法，其出发点是：对于一个近乎有序的序列，插入排序的效率非常高。所以希尔排序使用较大的步长来模仿插入排序（后者步长为1），从而很快地对序列梳理至近乎有序的程度。
插入排序可以视作步长为1的希尔排序。
CODE
int* shellSort(int* A, int n) {
for (int gap = n / 2; gap > 0; gap /= 2) //步长
for (int i = gap; i < n; ++i){
int get=A[i];
int j=i-gap;
while(j >= 0 && A[j] > get){
A[j + gap] = A[j];
j -= gap;
}
A[j + gap] = get;
}
return A;
}
对比插入排序：
int* shellSort(int* A, int n) {
for (int gap = n/2; gap>0; gap /= 2) // [空]
for (int i = gap; i < n; ++i){ // for (int i = 1; i < n; ++i){
int get=A[i]; // int get=A[i];
int j=i-gap; // int j=i-1;
while(j >= 0 && A[j] > get){ // while(j>=0 && A[j]>get){
A[j + gap] = A[j]; // A[j+1]=A[j];
j -= gap; // j--;
} // }
A[j + gap] = get; // A[j+1]=get;
} // {
return A;
}
差异仅仅在于去掉了最外层的gap循环，然后gap取值为1.
附注
[2]早期的快排提供了另一种划分思路：
哨兵元素换到队尾，创建指针i和指针j分别指向首尾，并逐步向中间靠拢，指针i找到一个大于等于基准的元素，等待j指针找到一个小于等于基准的元素，两者交换。直到两指针相遇，换回哨兵元素。
然而这个过程看似简单，实则杀机四伏：
int* quickSort(int* A, int n) {
if(n<=1)
return A;
int pos=rand()%n;
swap(A[pos],A[n-1]);
//j指向A[n-1]而不是A[n-2]，否则在长度为2的数组中可能出错
int i=0,j=n-1;
//循环条件：i<j，这样在终止时i==j且i指向第一个大于哨兵的元素
while(i<j){
//A[i]=A[n-1]可以避免相等元素卡死的情况
while(i<j && A[i]<=A[n-1])
i++;
//A[j]=A[n-1]可以避免相等元素卡死的情况
while(i<j && A[j]>=A[n-1])
j--;
//i和j的调整顺序不要相反！
if(i<j)
swap(A[i],A[j]);
}
//终止时i==j且i指向第一个大于哨兵的元素
swap(A[i],A[n-1]);
//递归
quickSort(A,i);
quickSort(A+i+1,n-i-1);
return A;
}
