首页 > 代码库 > 双路快速排序法
双路快速排序法
1、算法出现的背景
之前讲的，当我们排序的是一个近乎有序的序列时，快速排序会退化到一个O(n^2)级别的排序算法，而对此的改进就是
引入了随机化快速排序算法；但是当我们的排序的是一个数值重复率非常高的序列时，此时随机化快速排序算法就不再起作用
了，而将会再次退化为一个O(n^2)级别的排序算法，那为什么会出现这种情况呢？且听下面的分析:
如上图所示就是之前分析的快速排序算法的partition的操作原理，我们通过判断此时i索引指向的数组元素e>v还是<v，
将他放在橙色或者是紫色两个不同的位置，然后将整个数组分成两个部分递归下去；但是这里其实我们是没有考虑=v的情况，
其实隐含的意思就是下面的两种情况:
其实从这里就可以看出来了，不管是>=v还是<=v，当我们的序列中存在大量重复的元素时，排序完成之后就会将整个数组序列
分成两个极度不平衡的部分，所以又退化到了O(n^2)级别的时间复杂度，这是因为对于每一个"基准"元素来说，重复的元素太多了，
如果我们选的"基准"元素稍微有一点的不平衡，那么就会导致两部分的差距非常大；即时我们的"基准"元素选在了一个平衡的位置，
但是由于等于"基准"元素的元素也非常多，也会使得序列被分成两个及其不平衡的部分，那么在这种情况下快速排序就又会退化成
O(n^2)级别的排序算法。如何解决呢？ 这就要用到今天讲的双路快速排序算法的原理了。
2、双路快速排序算法的原理
之前说的快速排序算法是将>v和<v的元素都放在了用来遍历序列的索引i所指向的元素e的左边，而我们的双路快速排序算法则不同，
他使用两个索引值（i、j）用来遍历我们的序列，将<v的元素放在索引i所指向的元素的左边，而将>v的元素放在索引j所指向的元素的
右边，这也正是双路排序算法的partition原理:
基本思想:
首先从左边的i索引往右边遍历，如果i指向的元素<v，那直接将i++移动到下一个位置，直道i指向的元素>=v则停止
然后使用j索引从右边开始往左边遍历，如果j指向的元素>v，那直接将j--移动到下一个位置，直道j指向的元素<=v则停止
此时i之前的元素都已经归并为<v的部分了，而j之后的元素也都已经归并为>v的部分了，此时只需要将arr[i]和arr[j]
交换位置即可
这样一样就不会存在大量的元素都集中在某一个部分的情况了。
将i++，j--开始遍历后后面的元素
3、双路快速排序算法的实现（基于C++）
1 /******************************** 双路快速排序算法实现 ***************************************/ 2 template<typename T> 3 T __partition2 (T arr[], int left, int right) 4 { 5 std::swap(arr[left], arr[std::rand() % (right - left + 1) + left]); // 这是之前随机化快速排序算法的核心 6 T v = arr[left]; 7 8 // 使用i索引从左到右遍历，使用j索引从右到左遍历 9 int i = left + 1; // i从第二个元素开始 10 int j = right; // j从最后一个元素开始 11 while (true) { 12 while ((i < right) && (arr[i] < v)) i++; // i从左往右遍历直道 arr[i] < v 13 while ((j > left + 1) && (arr[j] > v)) j--; // j从右往左遍历直道 arr[j] > v 14 if (i > j) break; // 退出循环的条件 15 std::swap(arr[i], arr[j]); // 将 arr[i] 与 arr[j] 交换位置 16 i++; // i++ j-- 17 j--; 18 } 19 20 std::swap(arr[left], arr[j]); // 最后将v放置到合适的位置 21 22 return j; 23 } 24 25 template<typename T> 26 void __quickSort2 (T arr[], int left, int right) 27 { 28 if (right - left <= 40) { 29 __insertSortMG<T>(arr, left, right); 30 return; 31 } 32 33 int p = __partition2<T>(arr, left, right); // 找到基准元素并返回基准元素所在的位置 34 __quickSort2<T>(arr, left, p - 1); // 对基准元素之前的序列调用__quickSort函数 35 __quickSort2<T>(arr, p + 1, right); // 对基准元素之后的序列调用__quickSort函数 36 } 37 38 template<typename T> 39 void quickSort2 (T arr[], int count) 40 { 41 std::srand(std::time(NULL)); // 种下随机种子 42 __quickSort2<T>(arr, 0, count - 1); // 调用__quickSort函数进行快速排序 43 } 44 /*********************************************************************************************/
4、性能测试
一般序列:
近乎有序的序列:
重复率非常高的序列:
双路快速排序法