一、快速排序算法的描述
算法导论，第7章
快速排序时基于分治模式处理的，
对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。
二、快速排序算法的基本特性
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
不稳定。
快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。
通常是用于排序的最佳选择。因为，排序最快，也只能达到O（nlgn）。
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r) //关键
3 QUICKSORT(A, p, q - 1)
4 QUICKSORT(A, q + 1, r)
数组划分
快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：PARTITION(A, p, r)
1 x ← A[r] //以最后一个元素，A[r]为主元
2 i ← p - 1
3 for j ← p to r - 1 //注，j从p指向的是r-1，不是r。
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
7 exchange A[i + 1] <-> A[r]
8 return i + 1
==============性感分割线===================
PARTITION(A, p, r)版本，可以改成下面这个版本
PARTITION(A, p, r) //请读者思考版本。
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r //让j 从p指向了最后一个元素r
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
//7 exchange A[i + 1] <-> A[r] 去掉此最后的步骤
8 return i //返回 i，不再返回 i+1.
ok，咱们来举一个具体而完整的例子。
来对以下数组，进行快速排序，
2 8 7 1 3 5 6 4(主元)
i p/j
2 8 7 1 3 5 6 4(主元)
j指的2<=4，于是i++，i也指到2，2和2互换，原数组不变。
j后移，直到指向1..
j（指向1）<=4，于是i++，i指向了8，所以8与1交换。
数组变成了：
i j
2 1 7 8 3 5 6 4
j后移，指向了3,3<=4，于是i++，i这是指向了7，于是7与3交换。
数组变成了：
i j
2 1 3 8 7 5 6 4
j继续后移，发现没有再比4小的数，所以，执行到了最后一步，
即上述PARTITION(A, p, r)代码部分的 第7行。
因此，i后移一个单位，指向了8
i j
2 1 3 8 7 5 6 4
A[i + 1] <-> A[r]，即8与4交换，所以，数组最终变成了如下形式，
2 1 3 4 7 5 6 8
ok，快速排序第一趟完成。
4把整个数组分成了俩部分，2 1 3,7 5 6 8，再递归对这俩部分分别快速排序。
i p/j
2 1 3(主元)
2与2互换，不变，然后又是1与1互换，还是不变，最后，3与3互换，不变，
最终，3把2 1 3，分成了俩部分，2 1，和3.
再对2 1，递归排序，最终结果成为了1 2 3.
7 5 6 8(主元)，7、5、6、都比8小，所以第一趟，还是7 5 6 8，
不过，此刻8把7 5 6 8，分成了 7 5 6，和8.[7 5 6->5 7 6->5 6 7]
再对7 5 6，递归排序，最终结果变成5 6 7 8。
ok，所有过程，全部分析完成。
由此可以得到快排的一个不变式：
对于任何数组下标k，有：
（1）如果 p<=k<=i,则A[k]<=x;
（2）如果i+1<=k<=j-1，则A[k]>x;
（3）如果k=r，则A[k]=x;
四、代码实现
void swap(int A[],int i, int j)
{
DType t = A[i];
A[i] = A[j];
A[j] = t;
}
void QKSort(int A[],int l,int u){
if(l>=u)
return ;
int i=l-1;
int x=A[u];
int tmp;
for(int j=l;j<u;j++){
if(A[j]<=x){
i++;
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
}
}
i++;
swap(A,i,u);
QKSort(A,l,i-1);
QKSort(A,i+1,u);
}
void Single_QKSort2(int A[],int l,int u){
cout<<"test"<<endl;
if(l>=u)
return ;
int i=l-1;
int x=A[u];
int tmp;
for(int j=l;j<=u;j++){
if(A[j]<=x){
i++;
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
}
}
Single_QKSort(A,l,i-1);
Single_QKSort(A,i+1,u);
} |
五、快速排序的最坏情况和最快情况。（下面的内容来自
精通八大排序算法系列：一、快速排序算法）
最坏情况发生在划分过程产生的俩个区域分别包含n-1个元素和一个0元素的时候，
即假设算法每一次递归调用过程中都出现了，这种划分不对称。那么划分的代价为O（n），
因为对一个大小为0的数组递归调用后，返回T（0）=O（1）。
估算法的运行时间可以递归的表示为：
T（n）=T（n-1）+T（0）+O（n)=T(n-1)+O(n).
可以证明为T（n）=O（n^2）。
因此，如果在算法的每一层递归上，划分都是最大程度不对称的，那么算法的运行时间就是O（n^2）。
亦即，快速排序算法的最坏情况并不比插入排序的更好。
此外，当数组完全排好序之后，快速排序的运行时间为O（n^2）。
而在同样情况下，插入排序的运行时间为O（n）。
//注，请注意理解这句话。我们说一个排序的时间复杂度，是仅仅针对一个元素的。
//意思是，把一个元素进行插入排序，即把它插入到有序的序列里，花的时间为n。
再来证明，最快情况下，即PARTITION可能做的最平衡的划分中，得到的每个子问题都不能大于n/2.
因为其中一个子问题的大小为|_n/2_|。另一个子问题的大小为|-n/2-|-1.
在这种情况下，快速排序的速度要快得多。为，
T(n)<=2T（n/2）+O（n）.可以证得，T（n）=O（nlgn）。
直观上，看，快速排序就是一颗递归数，其中，PARTITION总是产生9:1的划分，
总的运行时间为O（nlgn）。各结点中示出了子问题的规模。每一层的代价在右边显示。
每一层包含一个常数c。
快速排序的平均情况运行时间与其最佳情况运行时间很接近，而不是非常接近与其最坏情况运行时间，这点可以从上图中分析得到。
六、Hoare版本 即双向划分
使用双向划分可以避免所有元素都相同时，所用时间为O(n2)的情况！循环不变式如下：
下标i和j初始化为待划分数组的两端。主循环中有两个内循环，第一个循环讲i向右移过小元素，遇到大元素时停止；第二个内循环将j向左移过大元素，遇到小元素时停止。然后主循环测试这两个下标是否交叉并交换它们的值！
代码如下：
//可以避免所有元素都相同时，所用时间为O(n2)的情况！
void Double_QKSort(int A[],int l,int u){
cout<<"test"<<endl;
if(l>=u)
return ;
int x= A[l];
int tmp;
int i=l;
int j=u+1;
while(1){
do {
j--;
}while(A[j]>x&&j>i);
do{
i++;
}while(A[i]<x);
if(i>j)
break;
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
}
swap(A,l,j);
Double_QKSort(A,l,j-1);
Double_QKSort(A,j+1,u);
} |
（1）、选择中间元素为主元
void QuickSort(int data[],int lo,int hi)
{
int pivot,l,r,temp;
l = lo;
r = hi;
pivot=data[(lo+hi)/2]; //取中位值作为分界值
while(l<r)
{
while(data[l]<pivot)
++l;
while(data[r]>pivot)
--r;
if(l>=r)
break;
temp = data[l];
data[l] = data[r];
data[r] = temp;
++l;
--r;
}
if(l==r)
l++;
if(lo<r)
QuickSort(data,lo,l-1);
if(l<hi)
QuickSort(data,r+1,hi);
}
|
（2）、随机化版本
//交换两个元素值，咱们换一种方式，采取引用“&”
void swap(int& a , int& b)
{
int temp = a;
a = b;
b = temp;
}
//返回属于[lo,hi)的随机整数
int rand(int lo,int hi)
{
int size = hi-lo+1;
return lo+ rand()%size;
}
//分割，换一种方式，采取指针a指向数组中第一个元素
int RandPartition(int* data, int lo , int hi)
{
//普通的分割方法和随机化分割方法的区别就在于下面三行
swap(data[rand(lo,hi)], data[lo]);
int key = data[lo];
int i = lo;
for(int j=lo+1; j<=hi; j++)
{
if(data[j]<=key)
{
i = i+1;
swap(data[i], data[j]);
}
}
swap(data[i],data[lo]);
return i;
}
//逐步分割排序
void RandQuickSortMid(int* data, int lo, int hi)
{
if(lo<hi)
{
int k = RandPartition(data,lo,hi);
RandQuickSortMid(data,lo,k-1);
RandQuickSortMid(data,k+1,hi);
}
}
int main()
{
const int N = 100; //此就是上文说所的“极限”测试。为了保证程序的准确无误，你也可以让N=10000。
int *data = new int[N];
for(int i =0; i<N; i++)
data[i] = rand(); //同样，随机化的版本，采取随机输入。
for(i=0; i<N; i++)
cout<<data[i]<<" ";
RandQuickSortMid(data,0,N-1);
cout<<endl;
for(i=0; i<N; i++)
cout<<data[i]<<" ";
cout<<endl;
return 0;
} |
（3）、三数取中分割法
我想，如果你爱思考，可能你已经在想一个问题了，那就是，像上面的程序版本，其中算法导论上采取单向扫描中，是以最后一个元素为枢纽元素，即主元，而在Hoare版本及其几个变形中，都是以第一个元素、或中间元素为主元，最后，上述给的快速排序算法的随机化版本，则是以序列中任一一个元素作为主元。
那么，枢纽元素的选取，即主元元素的选取是否决定快速排序最终的效率列?
答案是肯定的，当我们采取data[lo],data[mid],data[hi]三者之中的那个第二大的元素为主元时，便能尽最大限度保证快速排序算法不会出现O（N^2）的最坏情况。这就是所谓的三数取中分割方法。当然，针对的还是那个Partition过程。
ok，直接写代码：
//三数取中分割方法
int RandPartition(int* a, int p , int q)
{
//三数取中方法的关键就在于下述六行，
int m=(p+q)/2;
if(a[p]<a[m])
swap(a[p],a[m]);
if(a[q]<a[m])
swap(a[q],a[m]);
if(a[q]<a[p])
swap(a[q],a[p]);
int key = a[p];
int i = p;
for(int j = p+1; j <= q; j++)
{
if(a[j] <= key)
{
i = i+1;
if(i != j)
swap(a[i], a[j]);
}
}
swap(a[i],a[p]);
return i;
}
void QuickSort(int data[], int lo, int hi)
{
if (lo<hi)
{
int k = RandPartition(data, lo, hi);
QuickSort(data, lo, k-1);
QuickSort(data, k+1, hi);
}
} |
（4）代码优化，使用随机版主元，对于小的子数组使用插入排序
int cutoff = 5;
void Rand_InsertSort_QKSort(int A[],int l,int u){
if(u-l<cutoff)
return ;
swap(A,l,randint(l,u));
int i=l,j=u+1;
int tmp,x=A[l];
while(1){
do{
j--;
}while(j>i&&A[j]>x);
do{
i++;
}while(A[i]<x);
if(j<i)
break;
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
}
swap(A,l,j);
Rand_InsertSort_QKSort(A,l,j-1);
Rand_InsertSort_QKSort(A,j+1,u);
}
|
八、非递归版本
template <class T>
int RandPartition(T data[],int lo,int hi)
{
T v=data[lo];
while(lo<hi)
{
while(lo<hi && data[hi]>=v)
hi--;
data[lo]=data[hi];
while(lo<hi && data[lo]<=v)
lo++;
data[hi]=data[lo];
}
data[lo]=v;
return lo;
}
//快速排序的非递归算法
template <class T>
void QuickSort(T data[],int lo,int hi)
{
stack<int> st;
int key;
do{
while(lo<hi)
{
key=partition(data,lo,hi);
//递归的本质是什么?对了，就是借助栈，进栈，出栈来实现的。
if( (key-lo)<(hi-key) )
{
st.push(key+1);
st.push(hi);
hi=key-1;
}
else
{
st.push(lo);
st.push(key-1);
lo=key+1;
}
}
if(st.empty())
return;
hi=st.top();
st.pop();
lo=st.top();
st.pop();
}while(1);
} |
八、含重复值的快速排序
待排序的文件中若有大量的重复值时，我们前面所考虑的快排算法的效率就会变得不可思议！
一个直接的想法是将文件分成三个部分：一个是比划分元素小的；一部分是和划分元素一样大的；另一部分划分元素大；
完成这样的划分过程比完成两路划分过程更复杂。流行的解决方法是Dijkstra的“荷兰国旗问题”很流行；
Bentley和Mcllroy发明了一个很好的三路划分方法。改动如下：
扫描时将遇到的左子文件中与划分元素相等的元素放到文件的最左边，将遇到的右边自文件中与划分元素相等的元素放到文件的最右边。划分过程中，保证有这样一种情形：
代码如下：
template <class Item>
int operator==(const Item &A,const Item &B){
return !less(A,B) && !less(B,A);
}
template <class Item>
void quicksort(Item a[],int l,int r){
int k;
Item v=a[r];
if(r<=l)
return;
int i=l-1,j=r,p=l-1,q=r;
for(;;){
while (a[++i]<v)
;
while (v<a[--j])
if(j==l)
break;
if(i>=j)
break;
exch(a[i],a[j]);
if(a[i]==v){
p++;
exch(a[p],a[i]);
}
if(v==a[j]){
q--;
exch(a[q],q[j]);
}
}
exch(a[i],a[r]);
j=i-1;
i=i+1;
for(k=l;k<=p;k++,j--)
exch(a[k],a[j]);
for(k=r-1;k>=q;k--,i++)
exch(a[k],a[i]);
quicksort(a,l,j);
quicksort(a,i,r);
} |
问题描述：
我们将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。如下图所示：
![]()
这个问题，类似快排中partition过程。不过，要用三个指针，一前begin，一中current，一后end，俩俩交换。
1、current遍历，整个数组序列，current指1不动，
2、current指0，与begin交换，而后current++，begin++，
3、current指2，与end交换，而后，current不动，end--。
为什么，第三步，current指2，与end交换之后，current不动了列，对的，正如algorithm__所说：current之所以与begin交换后，current++、begin++，是因为此无后顾之忧。而current与end交换后，current不动，end--，是因有后顾之忧。
为什么啊，因为你想想啊，你最终的目的无非就是为了让0、1、2有序排列，试想，如果第三步，current与end交换之前，万一end之前指的是0，而current交换之后，current此刻指的是0了，此时，current能动么？不能动啊，指的是0，还得与begin交换列。
ok，说这么多，你可能不甚明了，直接引用下gnuhpc的图，就一目了然了：
![]()
![]()
本程序主体的代码是：
//引用自gnuhpc
while( current<=end )
{
if( array[current] ==0 )
{
swap(array[current],array[begin]);
current++;
begin++;
}
else if( array[current] == 1 )
{
current++;
}
else //When array[current] =2
{
swap(array[current],array[end]);
end--;
}
}
看似，此问题与本文关系不大，但是，一来因其余本文中快速排序partition的过程类似，二来因为此问题引发了一段小小的思考，并最终成就了本文。差点忘了，还没回答本文开头提出的问题。所以，快速排序算法是如何想到的，如何一步一步发明的列?答案很简单：多观察，多思考。
阅读(2756) | 评论(0) | 转发(1) |
