您好,登錄后才能下訂單哦!
書(shū)接上文,上次講到了雙路快速排序,雙路快速排序是將等于v(標(biāo)志數(shù))的數(shù)也進(jìn)行交換,從而避免了在處理有大量重復(fù)數(shù)據(jù)的數(shù)組分組時(shí)的不平衡。而三路快速排序則是將等于v的數(shù)也分成一組,同樣可以解決上述問(wèn)題。其原理如下:
1、采用隨機(jī)排序的方法將某個(gè)數(shù)作為分割數(shù),放在數(shù)組開(kāi)頭,該數(shù)定義為v。將小于v的一段數(shù)組開(kāi)頭的數(shù)索引定義為lt,將需要遍歷的數(shù)組的索引定義為i,將小于v的一段數(shù)組的索引定義為gt,數(shù)組的開(kāi)頭和結(jié)尾的索引分別為l和r。原理圖如下:
2、對(duì)索引i進(jìn)行維護(hù),逐個(gè)比較索引i對(duì)應(yīng)的數(shù)與v的關(guān)系。如果arr[i]<v,那么將arr[i]和arr[lt+1]交換,之后將索引i和lt分別向后移動(dòng)一位。如下圖藍(lán)色的e和灰綠色的那塊相交換
3、如果arr[i]=v,則將arr[i]納入等于v的那一部分,之后將索引i向后移動(dòng)一位
4、如果arr[i]>v,則將arr[i]與arr[gt-1]交換位置,之后將索引gt向前移動(dòng)一位,但是要注意,這時(shí),索引i不需要移動(dòng),因?yàn)榻粨Q過(guò)來(lái)的數(shù)不知道大小,下一步還需要接著判斷。
5、按照這個(gè)流程,gt會(huì)和i重合,則結(jié)束比較的過(guò)程
6、最后,不要忘了將arr[l]和arr[lt]交換位置,注意:這里交換位置的是arr[lt]。排序完成
代碼如下:
#ifndef QUICKSORT3_H #define QUICKSORT3_H //三路快速排序算法 #include <iostream> #include <stdlib.h> using namespace std; template <typename T> void __QuickSort3way(T *arr,int l,int r) { //遞歸的終止條件 if (l>=r) { return; } else { //隨機(jī)快速排序選取的隨機(jī)值,為了避免在整體大致有序的情況下產(chǎn)生分組不平衡現(xiàn)象,使算法退化 int RAND = (rand() % (r - l) + l); swap(arr[l], arr[RAND]); T v = arr[l]; //小于v的分組的初始索引 int lt = l; //大于v的分組的初始索引 int gt = r + 1; //等于v的分組的初始索引,并且,此索引是數(shù)組遍歷值的索引 int i = l + 1; while (i<gt) { //如果遍歷的數(shù)據(jù)小于v if (arr[i]<v) { //將該數(shù)組與第一個(gè)等于v的數(shù)據(jù)交換 swap(arr[lt + 1], arr[i]); //維護(hù)小于v的索引和待遍歷的數(shù)據(jù)的索引 lt++; i++; } //如果數(shù)據(jù)大于v else if (arr[i]>v) { //交換該數(shù)與大于v的第一個(gè)數(shù),但是在這里不需要維護(hù)i的索引 swap(arr[i], arr[gt - 1]); gt--; } else//arr[i]==v { i++;//直接維護(hù)i的索引 } } //最后將數(shù)組第一個(gè)數(shù)v和小于v的最后一個(gè)數(shù)互換 swap(arr[l],arr[lt]); __QuickSort3way(arr,l,lt); __QuickSort3way(arr,gt,r); } } template <typename T> void QuickSort3way(T *arr,int n) { __QuickSort3way(arr, 0, n - 1); } #endif // !QUICKSORT3_H
以上就是本文的全部?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)容。