本文实例为大家分享了C/C++实现双路快速排序算法的具体代码,供大家参考,具体内容如下
看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂。这里写一下自己的理解过程,也加深一下自己的理解。
首先说一下为什么需要双路排序,在有些带有许多重复数据的数组里,使用随机快速排序或者最简单的快速排序算法时,由于重复的数据会放在原来的索引位置不动,就回导致划分数组时划分的某一部分太长,起不到分段排序的效果,这样就导致算法退化成O(n^2)的复杂度。就像下图:
为了解决这个问题,双路快速排序采用的方法是对等于v的数也进行交换,原理如下所述:
首先选择一个数作为标志,放在数组的最左侧,下标为l,在数组左边放小于v的数,右侧放大于v的数。
之后,先从l+1开始遍历数组,当数据小于v时,该数据属于左侧橙色部分,保持其位置不动,i++,继续向后遍历,当找到某个数大于或者等于(注意,这里等于很重要)v时,停止遍历。转而开始根据j来遍历数组,j不断减小,索引数组的数据,当索引到某个数小于或者等于v时,停止遍历。如下图所示:
这时两个绿色的区域就是分别属于<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; }
双路快速排序算法 QuickSort2.h
#ifndef QUICKSORT2_H #define QUICKSORT2_H #include <stdlib.h> #include <iostream> using namespace std; template <typename T> int __partition3(T *arr, int l, int r) { //此处结合随机快速排序的算法进行了优化,标记点在数组里随机选择 int RAND = (rand() % (r - l + 1) + l); swap(arr[RAND], arr[l]); int v = arr[l]; int i = l + 1; int j = r; while (true) { while (i <= r&&arr[i] < v) i++; while (j >= l + 1 && arr[j] > v) j--; if (i > j) { break; } swap(arr[i], arr[j]); i++; j--; } swap(arr[l], arr[j]); return j; } template <typename T> void __QuickSort2(T *arr,int l,int r) { if (l>=r) { return; } int p = __partition3(arr, l, r); __QuickSort2(arr, l, p - 1); __QuickSort2(arr, p + 1, r); } template <typename T> void QuickSort2(T *arr, int n) { __QuickSort2(arr, 0,n-1); } #endif
随机快速排序 RadomQuickSort.h
#ifndef RADOMQUICKSORT_H #define RADOMQUICKSORT_H #include <iostream> #include <stdlib.h> using namespace std; template <typename T> int __Randpartition(T *arr, int l, int r) { //选择开头的数作为分割的数 int RAND = arr[rand() % (r - l + 1) + l]; swap(arr[l], RAND); int i = arr[l]; //遍历数组,使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l] int j = l; //如果当前数据大于arr[l],就无需改变位置,如果小于arr[l],就将当前数据与分割点的数据后一个数据交换 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步,要记得将arr[l]和找到的分割点数据交换 swap(arr[l], arr[j]); return j; } template <typename T> void __RadomQuickSort(T *arr, int l, int r) { if (l >= r) { return; } int p = __Randpartition(arr, l, r); __RadomQuickSort(arr, l, p - 1); __RadomQuickSort(arr, p + 1, r); } template <typename T> void RadomQuickSort(T *arr, int n) { __RadomQuickSort(arr, 0, n - 1); } #endif
快速排序 QuickSort.h
#ifndef QUICKSORT_H #define QUICKSORT_H using namespace std; template <typename T> int __partition(T *arr, int l, int r) { //选择开头的数作为分割的数 int i = arr[l]; //遍历数组,使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l] int j = l; //如果当前数据大于arr[l],就无需改变位置,如果小于arr[l],就将当前数据与分割点的数据后一个数据交换 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步,要记得将arr[l]和找到的分割点数据交换 swap(arr[l], arr[j]); return j; } template <typename T> void __QuickSort(T *arr, int l, int r) { if (l >= r) { return; } int p = __partition(arr, l, r); __QuickSort(arr, l, p - 1); __QuickSort(arr, p + 1, r); } template <typename T> void QuickSort(T *arr, int n) { __QuickSort(arr, 0, n - 1); } #endif
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/483011.html