本文实例为大家分享了C/C++实现双路快速排序算法的具体代码，供大家参考，具体内容如下
看了刘宇波的视频，讲双路快速排序的，原理讲的很直观，程序讲解也一看就懂。这里写一下自己的理解过程，也加深一下自己的理解。
首先说一下为什么需要双路排序，在有些带有许多重复数据的数组里，使用随机快速排序或者最简单的快速排序算法时，由于重复的数据会放在原来的索引位置不动，就回导致划分数组时划分的某一部分太长，起不到分段排序的效果，这样就导致算法退化成O(n^2)的复杂度。就像下图：
为了解决这个问题，双路快速排序采用的方法是对等于v的数也进行交换，原理如下所述：
首先选择一个数作为标志，放在数组的最左侧，下标为l，在数组左边放小于v的数，右侧放大于v的数。
之后，先从l+1开始遍历数组，当数据小于v时，该数据属于左侧橙色部分，保持其位置不动，i++,继续向后遍历，当找到某个数大于或者等于（注意，这里等于很重要）v时，停止遍历。转而开始根据j来遍历数组，j不断减小，索引数组的数据，当索引到某个数小于或者等于v时，停止遍历。如下图所示：
这时两个绿色的区域就是分别属于
之后，将i,j分别向后向前移动一位，继续开始新的索引，直到i和j重合或者i>j位置，就完成了partition的过程。
下面贴出代码：
主函数 main.cpp
// QuickSort2.cpp : 双路快速排序，适用于解决有很多重复数据的数组。
//
#include "stdafx.h"
#include "E:/学习/C++/数据结构和算法/code/算法/排序算法/common/sortTestHelper.h"
#include "QuickSort.h"
#include "RadomQuickSort.h"
#include "QuickSort2.h"
using namespace std;
int main()
{
int n = 100000;
int *arr1 = SortTestHelper::generateRadomArray(n, 0, 50);
int *arr2 = SortTestHelper::generateRadomArray(n, 0, 50);
int *arr3 = SortTestHelper::generateRadomArray(n, 0,50);
SortTestHelper::sortTime("随机快速排序", RadomQuickSort, arr1, n);
SortTestHelper::sortTime("快速排序", QuickSort, arr2, n);
SortTestHelper::sortTime("双路快速排序", QuickSort2, arr3, n);
delete[] arr1;
delete[] arr2;
delete[] arr3;
return 0;
}另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
