排序方法已经学了不少了，是时候总结下各种排序，在我看来排序总共分为两种，基于比较的排序和不基于比较的排序。当然这是一种分类，也可以按照排序是否稳定分类。
基于比较的排序
这里先要说明，基于比较的排序(comparsion-based algorithm)最优时间复杂度为$O(nlogn)$,证明如下：
对于每次比较，相当于一个三叉的决策树，此树的高h=(log3(n!))=log3e.ln(n!)，由stirling逼近公式得h>=O(nlogn).
冒泡排序(bubbleSort)
每个人对冒泡排序并不陌生，相信每个人都可以轻松地写出来，对此不再赘述，仅给出实现。
void bubbleSort(vector<int>& A){
bool sorted=false;int n=A.size();
while(!sorted){
sorted=true;
for(int i=1;i<n;++i){
if(A[i]<A[i-1])
swap(A[i],A[i-1]);
}
n--;
}
}
|
插入排序(insertionSort)
插入排序，每次排序将后面未就绪的数不断插入到前面已就绪的数中。
void insertionSort(vector<int>& A){
for(int j=1;j<A.size();++j){
int key=A[j],i=j-1;
while(i>=0&&key<=A[i]){
A[i+1]=A[i--];
}
A[i+1]=key;
}
}
|
我们分析下他的时间复杂度$O(n^2)$,和冒泡相比并未得到改变，其实仔细观察下每次迭代，都需要在前面已就绪的位置查找，对于有序向量的查找，我们可以采用二分查找，(误)时间复杂度为$O(logn)$,总复杂度达到$O(nlogn)$,已达最优下界。由于向量插入也需要$O(n)$的操作，所以时间复杂度仍为$O(n^2)$.
具体实现如下：
int binSearch(vector<int>& A,int &key,int lo=0,int hi=A.size()){
while(lo<hi){
int mi=(lo+hi)>>1;
(key<A[mi])?hi=mi:lo=mi+1;
}
return --lo;
}
void insert(vector<int>& A,int key,int lo,int hi){
while(hi>lo)
A[hi]=A[hi-1];
A[lo]=key;
}
void insertionSort(vector<int>& A){
for(int i=1;i<A.size();++i){
int key=A[i];
insert(A,key,binSearch(A,key,0,i),i);
}
}
|
选择排序(selectionSort)
选择排序和插入排序正相反，他是在前面中未就绪元素中选取最大值，插入在至后面已就绪的位置。
具体实现如下：
int max(int lo,int hi){
int maxNum=hi;
while(lo<hi--)
if(A[hi]>A[maxNum])
maxNum=hi;
return maxNum;
}
void selectionSort(vector<int>& A,int lo=0,int hi=A.size()){
while(lo<--hi){
swap(A[max(lo,hi)],A[hi]);
}
}
|
时间复杂度为$O(n^2)$,
归并排序(mergeSort)
介绍了几个时间复杂度为$O(n^2)$的算法，下面开始介绍时间复杂度为$O(nlogn)$的算法。
归并排序是典型的分治算法(divide and conquer),首先他将原序列分解为单独的单个元素，然后再不断合并各个子序列。
实现如下：
void mergeSort(vector<int>& A,int lo,int hi){
if(hi-lo<2) return ;
int mi=(lo+hi)>>1;
mergeSort(A,lo,mi); mergeSort(A,mi,hi);
merge(A,lo,mi,hi);
}
void merge(vector<int>& _elem,int lo,int mi,int hi){
int *A=_elem+lo;
int lb=mi-lo; int *B=new int[lb];
for(int i=0;i<lb;B[i]=A[i++]);
int lc=hi-mi;int *C=_elem+mi;
for(int i=0,j<0,k=0;j<lb;){
if((lc<=k)||B[j]<=C[k]) A[i++]=B[j++];
if((k<lc)&&C[k]<B[j]) A[i++] = C[k++];
}
}
|
对于时间复杂度的分析如下：
$T(n)=2O(n/2)+O(n)$
$T(1)=O(1)$
得$T(n)/n=O(n/2)/(n/2)+O(1)$
若$S(n)=T(n)/n$
则
$S(n)=S(n/2)+O(1)$
$S(n)=S(n/4)+O(2)$
·····
$S(n)=S(n/2^k)+O(k)=O(logn)$
所以有$T(n)=S(n)n=O(nlogn)$
时间复杂度为O(nlogn),前面已经证明$O(nlogn)$已经为基于比较的最优下界。
快速排序
快速排序和归并排序类似，都是分治思想，不过归并主要时间消耗在合并，快排主要时间消耗在划分子序列。
实现如下：
int partition(int* A,int lo,int hi){
int pivot=A[lo];
while(lo<hi){
while((lo<hi)&&(pivot<=A[hi])) hi--;
A[lo]=A[hi];
while((lo<hi)&&(A[lo]<=pivot)) lo++;
A[hi]=A[lo];
}
A[lo]=pivot;
return lo;
}
void quickSort(int *A,int lo,int hi){
if(hi-lo<2) return ;
int mi=partition(A,lo,hi-1);
quickSort(A,lo,mi);
quickSort(A,mi+1,hi);
}
|
平均时间复杂度为O(nlogn).
堆排序
const int maxn=1000;
int sz=0;
int heap[maxn];
void push(int x){
int i=sz++;int p;
while(i>0){
p=(i-1)/2;
if(heap[p]<x) break;
heap[i]=heap[p];
i=p;
}
heap[i]=x;
}
int pop(){
int x=heap[--sz];
int res=heap[0];
int i=0;
while(i*2+1<sz){
int a=i*2+1,b=i*2+2;
if(heap[a]>heap[b]) swap(a,b);
if(heap[a]>=x) break;
heap[i]=heap[a];
i=a;
}
heap[i]=x;
return res;
}
|
非基于比较的排序
计数排序(countingSort)
基数排序(radixSort)
桶排序(bucketSort)