本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f%e5%88%86%e6%9e%90/
快速排序是比较经典的算法，所以我把在编程珠玑上的讲解整理了一下，也当给自己理清思路。在某些特定情况下，在空间和时间上应该还有很多优化的策略，所以以后会继续学习优化的方法。
一、单向划分的快排实现
该程序不会导致无限递归调用，因为每次都排除了x[m],与二分搜索会终止的原理一样。 当输入数组是不同元素的随机排列时，该快速排序的平均时间复杂度是O(n log n),栈空间为O(log n).任何基于比较的排序至少需要O( n log n)次比较，因此快速排序接近最优算法。 c库函数的快速排序算法的通用接口开销很大，所以本程序可能适合与一些表现良好的应用程序，但在一些常见的输出下，本程序可能会退化为平方时间算法。
#include<iostream>
using namespace std;
int x[100];
void qsort1(int l , int u)
{
if(l >= u)
return ;
int m = l;
for(int i = l + 1; i <= u; i++)
{
if(x[i] < x[l])
swap(x[++m] , x[i]);
}
swap(x[l] , x[m]);
qsort1(l , m - 1);
qsort1(m + 1 , u);
}
int main()
{
int n;
cin>>n;
for(int i = 0; i < n;i++)
cin>>x[i];
qsort1(0 , n - 1);
for(int i = 0 ; i < n; i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
二、单向划分加哨兵优化 对qsort1的一点优化。将划分方案从右向左运行，由于循环结束时x[m] = t;所以可直接使用参数(l , m-1)和(m+1 , u)进行递归，不再需要swap操作，用x[l]作为哨兵还省去了内循环中的一次比较。
#include<iostream>
using namespace std;
int x[100];
void qsort2(int l , int u)
{
int i , m , t;
if(l >= u)
return ;
i = m = u + 1;
t = x[l];
do{
while(x[--i] < t)
;
swap(x[--m] , x[i]);
}while(i != l);
qsort2(l , m - 1);
qsort2(m + 1 , u);
}
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
cin>>x[i];
qsort2(0 , n - 1);
for(int i = 0 ; i < n; i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
三、双向划分的快速排序 n个相同元素组成的数组，对于这种输入，插入排序的性能比较好，每个与素需要移动的距离都是0，所以总的运行时间是O(n),但是qsort1算法的性能比较糟糕，n-1次的划分中每次划分都需要O(n)时间来去掉一个元素，所以总的运行时间是O(n^2)。使用双向划分可以避免这问题。采用双向划分，当输入元素相时，如果采用向右跳过避免多与操作的方式，还是会得到平方时间的算法（注意向右的do循环会执行到底）,正确的做法是当遇到相同元素是停止扫描，交换i和j 的元素值。这样做交换的次数增加了，但是将所有元素都同的最坏情况变成了差不多需要nlog2n次比较的最好情况。
#include<iostream>
using namespace std;
int x[100];
void qsort3(int l , int u)
{
if(l >= u)
return ;
int t = x[l];
int i = l;
int j = u + 1;
while(1){
do{
i++;
}while(i <= u && x[i] < t);
do{
j--;
}while(x[j] > t);
if(i > j)
break;
swap(x[i] , x[j]);
}
swap(x[l] , x[j]);
qsort3(l , j - 1);
qsort3(j + 1 , u);
}
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
cin>>x[i];
qsort3(0 , n - 1);
for(int i = 0 ; i < n; i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
四、采用随机化优化的快速排序 对于随机输入，以上算法没问题，但是对于某些输入，这种算法的时间和空间都偏多。例如，如果数组已经按升序排列好了，或者已经按降序排列好了，就会围绕最小或者最大，然后次小或次大划分下去，总共需要O(n^2)的时间。随机选择划分元素就可以得到好得多的性能，我们通过把x[l]和x[l…u]中的一个随机项想交换来实现这一点swap(l,randint(l , u));结合了随机划分元素和双向划分以后，对于任意输入，快排的期望运行时间都正比于nlog n,随机情况下的性能边界是通过调用随机数生成器得到的，而不是通过对输入的分布进行假设得到的。 用插入排序来排序很小的子数组，可以继续提高性能。 cutoff用以停止继续划分，一般选取cutoff为50。
#include<iostream>
using namespace std;
int x[100];
void isort3(int l , int u)
{
int j;
for(int i = l ; i <= u ;i++){
int t = x[i];
for(j = i ; j > 0 && x[j-1] > t ;j--)
x[j] = x[j-1];
x[j] = t;
}
}
int randint(int l , int u)
{
return l + rand()%(u - l);
}
void qsort4(int l , int u)
{
if(u - l < 50){
isort3(l , u);
return;
}
swap(x[l] , x[randint(l , u)]);
int t = x[l];
int i = l;
int j = u + 1;
while(1){
do{
i++;
}while(i <= u && x[i] < t);
do{
j--;
}while(x[j] > t);
if(i > j)
break;
swap(x[i] , x[j]);
}
swap(x[l] , x[j]);
qsort4(l , j - 1);
qsort4(j + 1 , u);
}
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
cin>>x[i];
qsort4(0 , n - 1);
for(int i = 0 ; i < n; i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
五、快速排序总结 C库函数qsort非常简单并且相对比较快，比我们自己写的快排慢，仅仅因为其通用灵活的接口对每次比较都是用函数调用。c++库函数sort具有最简单的接口：我们通过调用sort(x,x+n)对数组排序，其实现也非常高效，若系统的排序能满足我们的要求，就不用考虑自己编写代码了。
