0.前言
在《数据结构与算法分析》一书上，看到了两种不同的快速排序算法。一种十分简单，一种进行了优化。我想知道它们与C++ STL 自带的sort（也是快速排序），究竟谁比较快呢？
请注意，文中给出的时间都加上了生成随机数组的时间，生成1000万个随机数用时是0.349s。
1.简单的快速排序
这是最简单的快速排序的代码，我认为它甚至比选择冒泡插入三种简单排序算法还要简单。在对一千万个数字排序中取得的成绩是：5.253 5.18 5.285
void quickSort_simple(vector<int> &a)
{
if(a.size()>1)
{
vector<int> smaller;
vector<int> same;
vector<int> larger;
auto chosen=a[a.size()/2];
for(auto &i:a)
{
if(i<chosen)
smaller.push_back(i);
else if(i>chosen)
larger.push_back(i);
else
same.push_back(i);
}
quickSort_simple(smaller);
quickSort_simple(larger);
std::move(begin(smaller),end(smaller),begin(a));
std::move(begin(same),end(same),begin(a)+smaller.size());
std::move(begin(larger),end(larger),end(a)-larger.size());
}
}
2.C++自带的快速排序
可以发现正经的快速排序速度就快多了。
sort(a.begin(),a.end());
//3.883 3.919 3.923
3.经过优化的快速排序
void insertionSort(vector<int> &a,int left,int right)
{
for(int p=left+1;p<=right;p++)
{
int tmp=std::move(a[p]);
int j;
for(j=p;j>left&&tmp<a[j-1];--j)
{
a[j]=std::move(a[j-1]);
}
a[j]=std::move(tmp);
}
}
int& median3(vector<int> &a,int left,int right)
{
int center=(left+right)/2;
if(a[center]<a[left])
std::swap(a[left],a[center]);
if(a[right]<a[left])
std::swap(a[right],a[left]);
if(a[right]<a[center])
std::swap(a[right],a[center]);
std::swap(a[center],a[right-1]);//便于一趟快速排序,注意到我们保证了right位置上的数比pivot大了
return a[right-1];
}
void quickSort(vector<int> &a,int left,int right)
{
if(left+10<=right)//小大于10的数组才使用快速排序
{
int &pivot=median3(a,left,right);
int i=left,j=right-1;
for(;;)
{
while(a[++i]<pivot){}
while(pivot<a[--j]){}
if(i<j)
std::swap(a[i],a[j]);
else
break;
}
std::swap(a[i],a[right-1]);//让枢纽元回到它应该去的地方
quickSort(a,left,i-1);
quickSort(a,i+1,right);//i位置上的是枢纽元，已经对了
}
else
insertionSort(a,left,right);
}
void quickSort(vector<int> &a)
{
quickSort(a,0,a.size()-1);
}
它的效果甚至好于自带的sort，2.692 2.695 2.694， 首先是对枢纽元的选择，好的枢纽元使得速度快了大概14%（是的，书上给出了确切的数据）。
其次，当对于小数组，我们不在使用快速排序，而是用插入排序，也加快了速度。
4.总结
在C++中你的确可以造出很好的轮子，但是这是不必要的。