您好,登錄后才能下訂單哦!
本文實(shí)例為大家分享了C/C++實(shí)現(xiàn)雙路快速排序算法的具體代碼,供大家參考,具體內(nèi)容如下
看了劉宇波的視頻,講雙路快速排序的,原理講的很直觀,程序講解也一看就懂。這里寫一下自己的理解過程,也加深一下自己的理解。
首先說一下為什么需要雙路排序,在有些帶有許多重復(fù)數(shù)據(jù)的數(shù)組里,使用隨機(jī)快速排序或者最簡(jiǎn)單的快速排序算法時(shí),由于重復(fù)的數(shù)據(jù)會(huì)放在原來的索引位置不動(dòng),就回導(dǎo)致劃分?jǐn)?shù)組時(shí)劃分的某一部分太長(zhǎng),起不到分段排序的效果,這樣就導(dǎo)致算法退化成O(n^2)的復(fù)雜度。就像下圖:
為了解決這個(gè)問題,雙路快速排序采用的方法是對(duì)等于v的數(shù)也進(jìn)行交換,原理如下所述:
首先選擇一個(gè)數(shù)作為標(biāo)志,放在數(shù)組的最左側(cè),下標(biāo)為l,在數(shù)組左邊放小于v的數(shù),右側(cè)放大于v的數(shù)。
之后,先從l+1開始遍歷數(shù)組,當(dāng)數(shù)據(jù)小于v時(shí),該數(shù)據(jù)屬于左側(cè)橙色部分,保持其位置不動(dòng),i++,繼續(xù)向后遍歷,當(dāng)找到某個(gè)數(shù)大于或者等于(注意,這里等于很重要)v時(shí),停止遍歷。轉(zhuǎn)而開始根據(jù)j來遍歷數(shù)組,j不斷減小,索引數(shù)組的數(shù)據(jù),當(dāng)索引到某個(gè)數(shù)小于或者等于v時(shí),停止遍歷。如下圖所示:
這時(shí)兩個(gè)綠色的區(qū)域就是分別屬于<v和>v的部分,而i,j所對(duì)應(yīng)的索引數(shù)據(jù)要交換位置。
之后,將i,j分別向后向前移動(dòng)一位,繼續(xù)開始新的索引,直到i和j重合或者i>j位置,就完成了partition的過程。
下面貼出代碼:
主函數(shù) main.cpp
// QuickSort2.cpp : 雙路快速排序,適用于解決有很多重復(fù)數(shù)據(jù)的數(shù)組。 // #include "stdafx.h" #include "E:/學(xué)習(xí)/C++/數(shù)據(jù)結(jié)構(gòu)和算法/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("隨機(jī)快速排序", 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) { //此處結(jié)合隨機(jī)快速排序的算法進(jìn)行了優(yōu)化,標(biāo)記點(diǎn)在數(shù)組里隨機(jī)選擇 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
隨機(jī)快速排序 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; //如果當(dāng)前數(shù)據(jù)大于arr[l],就無需改變位置,如果小于arr[l],就將當(dāng)前數(shù)據(jù)與分割點(diǎn)的數(shù)據(jù)后一個(gè)數(shù)據(jù)交換 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步,要記得將arr[l]和找到的分割點(diǎn)數(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_H using 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; //如果當(dāng)前數(shù)據(jù)大于arr[l],就無需改變位置,如果小于arr[l],就將當(dāng)前數(shù)據(jù)與分割點(diǎn)的數(shù)據(jù)后一個(gè)數(shù)據(jù)交換 for (size_t k = j + 1; k <= r; k++) { if (arr[k]<i) { swap(arr[j + 1], arr[k]); j++; } } //最后一步,要記得將arr[l]和找到的分割點(diǎn)數(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)生一個(gè)從[rangeL,rangeH]的隨機(jī)數(shù)組,數(shù)組個(gè)數(shù)是n int* generateRadomArray(int n,int rangeL,int rangeH) { //為了算法的健壯性,需要判斷錯(cuò)誤輸入 assert(rangeL < rangeH); int* arr = new int[n]; //時(shí)間為種子的隨機(jī)數(shù) srand((unsigned)time(NULL)); for (int i = 0;i < n;i++) { //生成rangeL到rangeH之間的隨機(jī)數(shù)的算法 arr[i] = rand() % (rangeH - rangeL + 1) + rangeL; } return arr; } //產(chǎn)生近乎有序的隨機(jī)數(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ù)組元素的個(gè)數(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; } //計(jì)算程序運(yùn)行時(shí)間 template<typename T> //函數(shù)輸入?yún)?shù)是:所需要計(jì)算的運(yùn)行的函數(shù)的名稱,函數(shù)的指針,函數(shù)的輸入數(shù)組,輸入數(shù)組的個(gè)數(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<<"的運(yùn)行時(shí)間:" << double(endtime-startime) / CLOCKS_PER_SEC <<"s"<< std::endl; } //拷貝隨機(jī)生成的數(shù)組:輸入要拷貝的數(shù)組指針(整型),輸入需要拷貝多少個(gè)數(shù) int* copyarr(int* a, int n) { int *arr = new int[n]; copy(a,a+n, arr); return arr; } } #endif
最終結(jié)果三種算法對(duì)10萬個(gè)具有重復(fù)的數(shù)據(jù)的排序時(shí)間如下:
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。