C++中雙路快速排序算法的原理是什么，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

揚州ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！

首先說一下為什么需要雙路排序，在有些帶有許多重復數(shù)據(jù)的數(shù)組里，使用隨機快速排序或者最簡單的快速排序算法時，由于重復的數(shù)據(jù)會放在原來的索引位置不動，就回導致劃分數(shù)組時劃分的某一部分太長，起不到分段排序的效果，這樣就導致算法退化成O(n^2)的復雜度。就像下圖：

為了解決這個問題，雙路快速排序采用的方法是對等于v的數(shù)也進行交換，原理如下所述：

首先選擇一個數(shù)作為標志，放在數(shù)組的最左側，下標為l，在數(shù)組左邊放小于v的數(shù)，右側放大于v的數(shù)。之后，先從l+1開始遍歷數(shù)組，當數(shù)據(jù)小于v時，該數(shù)據(jù)屬于左側橙色部分，保持其位置不動，i++,繼續(xù)向后遍歷，當找到某個數(shù)大于或者等于（注意，這里等于很重要）v時，停止遍歷。轉而開始根據(jù)j來遍歷數(shù)組，j不斷減小，索引數(shù)組的數(shù)據(jù)，當索引到某個數(shù)小于或者等于v時，停止遍歷。如下圖所示：

這時兩個綠色的區(qū)域就是分別屬于<v和>v的部分，而i,j所對應的索引數(shù)據(jù)要交換位置。

之后，將i,j分別向后向前移動一位，繼續(xù)開始新的索引，直到i和j重合或者i>j位置，就完成了partition的過程。

下面貼出代碼：

主函數(shù) main.cpp

// QuickSort2.cpp : 雙路快速排序，適用于解決有很多重復數(shù)據(jù)的數(shù)組。//#include "stdafx.h"#include "E:/學習/C++/數(shù)據(jù)結構和算法/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){//此處結合隨機快速排序的算法進行了優(yōu)化，標記點在數(shù)組里隨機選擇 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){ //選擇開頭的數(shù)作為分割的數(shù) int RAND = arr[rand() % (r - l + 1) + l]; swap(arr[l], RAND); int i = arr[l]; //遍歷數(shù)組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l] int j = l; //如果當前數(shù)據(jù)大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數(shù)據(jù)與分割點的數(shù)據(jù)后一個數(shù)據(jù)交換 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步，要記得將arr[l]和找到的分割點數(shù)據(jù)交換 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_Husing namespace std;template <typename T>int __partition(T *arr, int l, int r){ //選擇開頭的數(shù)作為分割的數(shù) int i = arr[l]; //遍歷數(shù)組，使得arr[l,l+1,...j]<arr[l],arr[j+1,...,k)>arr[l] int j = l; //如果當前數(shù)據(jù)大于arr[l]，就無需改變位置，如果小于arr[l]，就將當前數(shù)據(jù)與分割點的數(shù)據(jù)后一個數(shù)據(jù)交換 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步，要記得將arr[l]和找到的分割點數(shù)據(jù)交換 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

SortTestHelper 函數(shù)

#ifndef SORTTESTHELPER_H#define SORTTESTHELPER_H#include <iostream>#include <cassert>#include <ctime>#include <string>using namespace std;namespace SortTestHelper {//產(chǎn)生一個從[rangeL,rangeH]的隨機數(shù)組，數(shù)組個數(shù)是n int* generateRadomArray(int n,int rangeL,int rangeH) { //為了算法的健壯性，需要判斷錯誤輸入 assert(rangeL < rangeH); int* arr = new int[n]; //時間為種子的隨機數(shù) srand((unsigned)time(NULL)); for (int i = 0;i < n;i++) { //生成rangeL到rangeH之間的隨機數(shù)的算法 arr[i] = rand() % (rangeH - rangeL + 1) + rangeL; } return arr; }//產(chǎn)生近乎有序的隨機數(shù) int *generateNearlyOrderedArray(int n, int swapnum) { int *arr = new int[n]; srand((unsigned)time(NULL)); for (size_t i = 0; i < n; i++) { arr[i] = i; } for (size_t i = 0; i < swapnum; i++) { int x = rand() % n; int y = rand() % n; swap(arr[x], arr[y]); } return arr; }//打印數(shù)組：輸入數(shù)組，數(shù)組元素的個數(shù) template<typename T> void printArr(T *arr,int n) { for (size_t i = 0; i < n; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; }//判斷是否已經(jīng)排序 template<typename T> bool ifSort(T *arr,int n) { for (size_t i = 0; i < n-1; i++) { if (arr[i]>arr[i+1]) { return false; } } return true; }//計算程序運行時間 template<typename T> //函數(shù)輸入?yún)?shù)是：所需要計算的運行的函數(shù)的名稱，函數(shù)的指針，函數(shù)的輸入數(shù)組，輸入數(shù)組的個數(shù) void sortTime(string funName,void(*sort)(T*arr, int), T* arr,int n) { clock_t startime = clock(); sort(arr,n); clock_t endtime = clock(); assert(ifSort(arr, n)); std::cout <<funName<<"的運行時間：" << double(endtime-startime) / CLOCKS_PER_SEC <<"s"<< std::endl; }//拷貝隨機生成的數(shù)組:輸入要拷貝的數(shù)組指針(整型)，輸入需要拷貝多少個數(shù) int* copyarr(int* a, int n) { int *arr = new int[n]; copy(a,a+n, arr); return arr; }}#endif

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

網(wǎng)站欄目：C++中雙路快速排序算法的原理是什么
當前地址：http://chinadenli.net/article14/jehhge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供App設計、標簽優(yōu)化、App開發(fā)、網(wǎng)站導航、微信公眾號、網(wǎng)站設計公司

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)