快速排序 详解（快速排序 双路快排 三路快排）

注：内容，图片来自于慕课网liuyubobobo老师的课程。

快速排序


快速排序可以说是20世纪最伟大的算法之一了。相信都有所耳闻，它的速度也正如它的名字那样，是一个非常快的算法了。当然它也后期经过了不断的改进和优化，才被公认为是一个值得信任的非常优秀的算法。

c++中algorithm中的sort一般都是用的快排（在快排恶化的情况下才会转换成其它的排序）。

核心思想：分治

 

 

下面我们来讲解一下快排的子过程的思路：

快速排序是把数组中的一个元素挪到它排好序时应该所处的位置，如图：



 

 

 

 

 

 


首先选择数组中的一个元素，比如用l索引指向最左边的元素v，逐渐遍历数组所有位于l左边的元素，在遍历的过程中，我们将逐渐整理出小于v的元素和大于v的元素，当然我们继续用一个索引j来记录小于v和大于v的分界点，然后我们当前访问的元素索引为i。



 

 

 

 

那么i怎么处理呢？很简单当i指向的元素e大于v的时候，直接包含进大于v的部分中，像这样：



 

 

 

 

 

然后我们继续讨论下一个元素，此时i++，如图：



 

 

 

 

 

如果元素e小于v的时候怎么做呢？只需要把元素e和橙色部分之后的一个元素交换，就可以了，此时索引j++。如图：







 

 

 

 

最后i继续往后走，到最后的时候就直接将数组分成了等于v，小于v，大于v的三部分。

最后将l位置和j位置交换，就实现了快速排序的子过程，如图：



 

下面是快速排序代码（使用template模板泛型是因为我们有的时候不仅仅是需要对int数组进行排序，还可能是浮点数，字符串，甚至是结构体，类进行排序）：
#include<iostream> #include<algorithm> using namespace std; template <typename
T> //对arr[l...r]进行partition操作 int partition(T arr[],int l,int r) { T v=arr[l];
int j; j=l; for(int i=l+1;i<=r;i++) { if(arr[i]<v) { swap(arr[j+1],arr[i]);
j++; } } swap(arr[l],arr[j]); return j; } //对arr[l...r]部分进行排序 template
<typename T> void __quicksort(T arr[],int l,int r) { if(l>=r) return ; int
p=partition(arr,l,r); __quicksort(arr,l,p-1); __quicksort(arr,p+1,r); }
template <typename T> void quicksort(T arr[],int n) { __quicksort(arr,0,n-1); }
int main() { int arr[100]; int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i];
quicksort(arr,n); for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<endl; return 0;
}

大家知道，快速排序虽然高效，但并不稳定，当数组中存在大量重复元素时，比如举个例子，我用模板测试归并排序和快速排序的时间，设置一个1000000的数组，数组元素在0-10之间随机取值，那么用归并需要花费0.290727s而快排需要花费171.151s，对，你没有看错。当快速排序最优的时候是o（nlgn），而此时显然退化到了o（n^2）的级别。这是为什么？


还记得上面我写的快排的子过程么，考虑到了e>v,e<v，而e=v的情况没有考虑对吧。看了代码理解了的同学应该清楚，其实我是把等于v这种情况包含进了大于v的情况里面了，那么会出现什么问题？
不管是当条件是大于等于还是小于等于v，当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边。

那么一种优化的方式便是进行双路快排。

 

 

双路快排（我看百度百科上面的快排题解c语言版好像用的就是双路快排）

 

和快排不同的是此时我们将小于v和大于v的元素放在数组的两端，那么我们将引用新的索引j的记录大于v的边界位置。如图：



 

 

 

 

 

i索引不断向后扫描，当i的元素小于v的时候继续向后扫描，直到碰到了某个元素大于等于v。j同理，直到碰到某个元素小于等于v。如图：



 

 

 

 

 

然后绿色的部分便归并到了一起，而此时只要交换i和j的位置就可以了，然后i++，j--就行了。如图：



 

 

 

 

 

直到i和j遍历完毕，整个数组排序完成。

这种优化当它遇到重复元素的时候，也能近乎将他们平分开来。

 

双路快排代码如下：
#include<iostream> #include<algorithm> using namespace std; template <typename
T> int partition(T arr[],int l,int r) { T v=arr[l]; int i,j; i=l+1;j=r;
while(true) { while(arr[i]<v&&i<=r)i++; while(j>=l+1&&arr[j]>v)j--;
if(i>j)break; swap(arr[i],arr[j]); i++; j--; } swap(arr[l],arr[j]); return j; }
template <typename T> void __quicksort2(T arr[],int l,int r) { if(l>=r) return
; int p=partition(arr,l,r); __quicksort2(arr,l,p-1); __quicksort2(arr,p+1,r); }
template <typename T> void quicksort(T arr[],int n) { __quicksort2(arr,0,n-1);
} int main() { int arr[100],n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i];
quicksort(arr,n); for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<endl; return 0;
}
 

当然除了快排和双路快排，还有一个更加经典的优化，我们叫它三路快排。

 

 

 

 

 

三路快排


双路快排将整个数组分成了小于v，大于v的两部分，而三路快排则是将数组分成了小于v，等于v，大于v的三个部分，当递归处理的时候，遇到等于v的元素直接不用管，只需要处理小于v，大于v的元素就好了。某一时刻的中间过程如下图：



 

 

 

 

 

当元素e等于v的时候直接纳入绿色区域之内，然后i++处理下一个元素。如图：



 

 

 

 

 

当元素e小于v的时候，只需要将元素e与等于e的第一个元素交换就行了，这和刚开始讲的快速排序方法类似。同理，当大于v的时候执行相似的操作。如图：





 

 

 

 

 

当全部元素处理完之后，数组便成了这个样子：



三路快排的代码如下：
#include<iostream> #include<algorithm> using namespace std; template <typename
T> void __quicksort3(T arr[],int l,int r) { if(l>=r) return ; T v=arr[l]; int
lt=l; int gt=r+1; int i=l+1; while(i<gt) { if(arr[i]<v)
{swap(arr[i],arr[lt+1]); lt++; i++;} else if(arr[i]>v) {
swap(arr[i],arr[gt-1]); gt--; } else { i++; } } swap(arr[l],arr[lt]);
__quicksort3(arr,l,lt-1); __quicksort3(arr,gt,r); } template <typename T> void
quicksort3(T arr[],int n) { __quicksort3(arr,0,n-1); } int main() { int
a[100],n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; quicksort3(a,n); for(int
i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
 

 

 

 

 

• « 上一篇：2017年年度小结和新年计划
• » 下一篇：Windows下安装PyTorch0.4.0