C/C++实现双路快速排序算法原理-创新互联

本文实例为大家分享了C/C++实现双路快速排序算法的具体代码，供大家参考，具体内容如下

看了刘宇波的视频，讲双路快速排序的，原理讲的很直观，程序讲解也一看就懂。这里写一下自己的理解过程，也加深一下自己的理解。

首先说一下为什么需要双路排序，在有些带有许多重复数据的数组里，使用随机快速排序或者最简单的快速排序算法时，由于重复的数据会放在原来的索引位置不动，就回导致划分数组时划分的某一部分太长，起不到分段排序的效果，这样就导致算法退化成O(n^2)的复杂度。就像下图：

为了解决这个问题，双路快速排序采用的方法是对等于v的数也进行交换，原理如下所述：

首先选择一个数作为标志，放在数组的最左侧，下标为l，在数组左边放小于v的数，右侧放大于v的数。
之后，先从l+1开始遍历数组，当数据小于v时，该数据属于左侧橙色部分，保持其位置不动，i++,继续向后遍历，当找到某个数大于或者等于（注意，这里等于很重要）v时，停止遍历。转而开始根据j来遍历数组，j不断减小，索引数组的数据，当索引到某个数小于或者等于v时，停止遍历。如下图所示：

这时两个绿色的区域就是分别属于v的部分，而i,j所对应的索引数据要交换位置。

之后，将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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。