一、为什么要用三路划分快排？
前面我们已经实现了三个版本的快速排序的算法，分别是hoare法，挖坑法和前后指针法。但是前面的三个版本的快速排序在某些极端场景中效率都会变得很低，例如大部分都是同一个数的时候，前面的三种方法都不能很高效地完成排序，时间复杂度退化成了O(N^2)，所以我们有必要对之前的排序方法进行一些改进，使它能够适应包含任何数据的数组。于是就有大佬想出了一个更牛的方法，那就是三路划分快排。
二、三路划分快排的思路
三路划分快排的思路：三路划分，顾名思义就是把数组分成三个部分进行排序，选定一个key，把数组分成小于key的，等于key的，还有大于key的。具体操作是：选定a[left]为key，再定义一个下标cur=left+1，一共就left，cur，right三个下标。从cur开始与key比较，如果a[cur]<key，就用a[cur]和a[left]交换，然后++left，++cur；如果a[cur]>key,就用a[cur]和a[right]交换，–right；如果a[cur]==key,那就++cur，这样循环往复，知道cur>right就结束，最后得到的a[begin,left-1]是比key小的数，a[left,right]是等于key的数，a[cur,end]是大于key的数，划分成三路之后，中间这一路就不用再进行排序了，因为中间这一路都是等于key的，所以已经有序了，只需要对左路和右路再进行递归排序即可。
动图演示如下：
显然，一趟排序之后把数组分成了小于key的，等于key的，还有大于key的。等于key的就不用再操作了，接下来就递归分别对小于key的数和大于key的数进行排序即可。
三、参考代码
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void PrintArr(int* a, int n) { int i = 0; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } //三数取中 int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) { return mid; } //来到这里证明a[mid]最小，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } else//a[left]<=a[mid] { if (a[mid] < a[right]) { return mid; } //来到这里证明a[mid]最大，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } } //三路划分快排 void ThreeWayQuickSort(int* a, int begin, int end) { //需要先定义局部的left和right进行++和--； //不能直接对begin和end操作，因为排完一趟 //之后需要利用begin和end来确定递归排序的 //边界 int left = begin; int right = end; //区间不存在就可以返回了 if (left >= right) { return; } //三数取中 int mid = GetMidNumi(a, left, right); if (mid != left) { Swap(&a[mid], &a[left]); } //选key int key = a[left]; int cur = left + 1; while (cur <= right) { //小于就和a[left]交换，保证小的数在key的左边 if (a[cur] < key) { Swap(&a[cur], &a[left]); left++; cur++; } //大于就和a[right]交换，保证大的数在key的右边 else if (a[cur] > key) { Swap(&a[cur], &a[right]); //只需要right--，不能cur++，证明看上图 right--; } else { cur++; } } //边界的确定看上图 ThreeWayQuickSort(a, begin, left - 1); ThreeWayQuickSort(a, cur, end); } int main() { int a[] = { 6,6,6,6,1,2,7,9,3,6,6,10,8 }; int sz = sizeof(a) / sizeof(a[0]); ThreeWayQuickSort(a, 0, sz - 1); PrintArr(a, sz); return 0; }
以上就是三路划分快排的所有内容了，这个快排可以说是不惧怕任意组合的数据的，无论所给的数组的数据有多么的极端，效率都能很高，这才是最牛的快速排序版本，你学会了吗？
