本文主要是介绍快排之三路划分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本⼆分居中，那么快排的递归树就是颗均匀的满⼆叉树，性能最佳。但是实践中虽然不可能每次都是⼆分居中，但是性能也还是可控的。但是如果出现每次选到最⼩值/最⼤值，划分为0个和N-1的⼦问题时，时间复杂度为O(N^2)，数组序列有序时就会出现这样的问题，我们前⾯已经⽤三数取中或者随机选key解决了这个问题，也就是说我们解决了绝⼤多数的问题，但是现在还是有⼀些场景没解决(数组中有⼤量重复数据时)，类似以下代码：
// 数组中有多个跟key相等的值
int a[] = { 6,1,7,6,6,6,4,9 };
int a[] = { 3,2,3,3,3,3,2,3 };
// 数组中全是相同的值
int a[] = { 2,2,2,2,2,2,2,2 };三路划分是快速排序的一种变体，三路划分的核⼼思想有点类似hoare的左右指针和lomuto的前后指针的结合，它在处理具有大量重复元素的数组时特别有效。在三路划分中，数组被分为三个部分：
- 小于基准key的元素
- 等于基准key的元素
- 大于基准key的元素
核⼼思想是把数组中的数据分为三段【⽐key⼩的值】 【跟key相等的值】【⽐key⼤的值】，所以叫做三路划分算法。结合下图，理解⼀下实现思想：
- key默认取left位置的值。
- left指向区间最左边，right指向区间最后边，cur指向left+1位置。
- cur遇到⽐key⼩的值后跟left位置交换，换到左边，left++，cur++。
- cur遇到⽐key⼤的值后跟right位置交换，换到右边，right--。
- cur遇到跟key相等的值后，cur++。
- 直到cur > right结束
通过以上的算法思路，我们就可以分成三路了
代码应用：
#include<iostream>
#include<vector>
using namespace std;void threeWayQuickSort(std::vector<int>& arr, int left, int right)
{if (left > right){return;}int lt = left;int rt = right;int randi = left + (rand() % (right - left + 1));swap(arr[left], arr[randi]);int cur = left + 1;int key = arr[left];while (cur <= right){if (arr[cur] > key){swap(arr[cur], arr[right]);right--;}else if (arr[cur] < key){swap(arr[cur], arr[left]);left++;cur++;}else{cur++;}}threeWayQuickSort(arr, lt, left - 1);threeWayQuickSort(arr, right + 1, rt);
}int main()
{vector<int> arr = { 9, -3, 5, 2, 6, 8, -6, 1, 3 };int n = arr.size();threeWayQuickSort(arr, 0, n - 1);for (int num : arr) {std::cout << num << " ";}return 0;
}
三路划分的主要优点是它减少了不必要的数据交换，特别是当数组中有很多重复元素时，这可以显著提高排序效率。此外，它也减少了递归的深度，因为相等的元素不需要被排序。
这篇关于快排之三路划分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
