目錄一、前言二、回顧單軸快排三、雙軸快排分析3.1、總體情況分析3.2、k交換過程3.3、收尾工作四、雙軸快排代碼一、前言

首選，雙軸快排也是一種快排的優(yōu)化方案，在JDK的Arrays.sort()中被主要使用。所以，掌握快排已經(jīng)不能夠滿足我們的需求，我們還要學(xué)會(huì)雙軸快排的原理和實(shí)現(xiàn)才行。

二、回顧單軸快排

單軸快排也就是我們常說的普通快速排序，對(duì)于快速排序我想大家應(yīng)該都很熟悉：基于遞歸和分治的，時(shí)間復(fù)雜度最壞而O(n2),最好和平均情況為O(nlogn).

而快排的具體思路也很簡(jiǎn)單，每次在待排序序列中找一個(gè)數(shù)(通常最左側(cè)多一點(diǎn))，然后在這個(gè)序列中將比他小的放它左側(cè)，比它大的放它右側(cè)。

如果運(yùn)氣肯不好遇到O(n)平方的，那確實(shí)就很被啦：

實(shí)現(xiàn)起來也很容易，這里直接貼代碼啦：

private static void quicksort(int [] a,int left,int right){ int low=left; int high=right; //下面兩句的順序一定不能混，否則會(huì)產(chǎn)生數(shù)組越界！！！very important！！！ if(low>high)//作為判斷是否截止條件 return; int k=a[low];//額外空間k，取最左側(cè)的一個(gè)作為衡量，最后要求左側(cè)都比它小，右側(cè)都比它大。 while(low<high)//這一輪要求把左側(cè)小于a[low],右側(cè)大于a[low]。 { while(low<high&&a[high]>=k)//右側(cè)找到第一個(gè)小于k的停止 { high--; } //這樣就找到第一個(gè)比它小的了 a[low]=a[high];//放到low位置 while(low<high&&a[low]<=k)//在low往右找到第一個(gè)大于k的，放到右側(cè)a[high]位置 { low++; } a[high]=a[low]; } a[low]=k;//賦值然后左右遞歸分治求之 quicksort(a, left, low-1); quicksort(a, low+1, right);}三、雙軸快排分析

咱們今天的主題是雙軸快排，雙軸和單軸的區(qū)別你也可以知道，多一個(gè)軸，前面講了快排很多時(shí)候選最左側(cè)元素以這個(gè)元素為軸將數(shù)據(jù)劃分為兩個(gè)區(qū)域，遞歸分治的去進(jìn)行排序。但單軸很多時(shí)候可能會(huì)遇到較差的情況就是當(dāng)前元素可能是最大的或者最小的，這樣子元素就沒有被劃分區(qū)間，快排的遞推T(n)=T(n-1)+O(n)從而為O(n2).

雙軸就是選取兩個(gè)主元素理想將區(qū)間劃為3部分，這樣不僅每次能夠確定元素個(gè)數(shù)增多為2個(gè)，劃分的區(qū)間由原來的兩個(gè)變成三個(gè)，最壞最壞的情況就是左右同大小并且都是最大或者最小，但這樣的概率相比一個(gè)最大或者最小還是低很多很多，所以雙軸快排的優(yōu)化力度還是挺大的。

3.1、總體情況分析

至于雙軸快排具體是如何工作的呢？其實(shí)也不難理解，這里通過一系列圖講解雙軸快排的執(zhí)行流程。

首先在初始的情況我們是選取待排序區(qū)間內(nèi)最左側(cè)、最右側(cè)的兩個(gè)數(shù)值作為pivot1和pivot2 .作為兩個(gè)軸的存在。同時(shí)我們會(huì)提前處理數(shù)組最左側(cè)和最右側(cè)的數(shù)據(jù)會(huì)比較將最小的放在左側(cè)。所以pivot1<pivot2.

而當(dāng)前這一輪的最終目標(biāo)是，比privot1小的在privot1左側(cè)，比privot2大的在privot2右側(cè)，在privot1和privot2之間的在中間。

這樣進(jìn)行一次后遞歸的進(jìn)行下一次雙軸快排，一直到結(jié)束，但是在這個(gè)執(zhí)行過程應(yīng)該去如何處理分析呢？需要幾個(gè)參數(shù)呢？

假設(shè)知道排序區(qū)間[start，end]。數(shù)組為arr， pivot1=arr[start],pivot2=arr[end] 還需要三個(gè)參數(shù)left，right和k。 l left初始為start，[start,left]區(qū)域即為小于等于pivot1小的區(qū)域(第一個(gè)等于)。 right與left對(duì)應(yīng)，初始為end，[right,end]為大于等于pivot2的區(qū)域(最后一個(gè)等于)。 k初始為start+1，是一個(gè)從左往右遍歷的指針，遍歷的數(shù)值與pivot1，pivot2比較進(jìn)行適當(dāng)交換，當(dāng)k>=right即可停止。

3.2、k交換過程

然后你可能會(huì)問k遍歷時(shí)候究竟怎么去交換？left和right該如何處理呢？不急我?guī)懵治觯紫菿是在left和right中間的，遍歷k的位置和pivot1，pivot2進(jìn)行比較：

如果arr[k]<pivot1,那么先++left，然后swap(arr,k,left),因?yàn)槌跏荚趕tart在這個(gè)過程不結(jié)束start先不動(dòng)。然后k++；繼續(xù)進(jìn)行

而如果arr[k]>pivot2.(區(qū)間自行安排即可)有點(diǎn)區(qū)別的就是right可能連續(xù)的大于arr[k],比如9 3 3 9 7如果我們需要跳過7前面9到3才能正常交換，這和快排的交換思想一致，當(dāng)然再具體的實(shí)現(xiàn)上就是right--到一個(gè)合適比arr[k]小的位置。然后swap(arr,k,right)切記此時(shí)k不能自加。因?yàn)閹Ы粨Q的那個(gè)有可能比pivot1還小要和left交換。

如果是介于兩者之間，k++即可

3.3、收尾工作

在執(zhí)行完這一趟即k=right之后，即開始需要將pivot1和pivot2的數(shù)值進(jìn)行交換

swap(arr, start, left);swap(arr, end, right);

然后三個(gè)區(qū)間根據(jù)編號(hào)遞歸執(zhí)行排序函數(shù)即可。

四、雙軸快排代碼

在這里，分享下個(gè)人實(shí)現(xiàn)雙軸快排的代碼：

import java.util.Arrays;public class 雙軸快排 { public static void main(String[] args) {int a[]= {7,3,5,4,8,5,6,55,4,333,44,7,885,23,6,44};dualPivotQuickSort(a,0,a.length-1);System.out.println(Arrays.toString(a)); } private static void dualPivotQuickSort(int[] arr, int start, int end) {if(start>end)return;//參數(shù)不對(duì)直接返回if(arr[start]>arr[end]) swap(arr, start, end);int pivot1=arr[start],pivot2=arr[end];//儲(chǔ)存最左側(cè)和最右側(cè)的值//(start，left]:左側(cè)小于等于pivot1 [right,end)大于pivot2int left=start,right=end,k=left+1;while (k<right) { //和左側(cè)交換 if(arr[k]<=pivot1) {//需要交換swap(arr, ++left, k++); } else if (arr[k]<=pivot2) {//在中間的情況k++; } else {while (arr[right]>=pivot2) {//如果全部小于直接跳出外層循環(huán) if(right--==k)break ;}if(k>=right)break ;swap(arr, k, right); }}swap(arr, start, left);swap(arr, end, right);dualPivotQuickSort(arr, start, left-1);dualPivotQuickSort(arr, left+1, right-1);dualPivotQuickSort(arr, right+1, end); } static void swap(int arr[],int i,int j) {int team=arr[i];arr[i]=arr[j];arr[j]=team; }}

執(zhí)行結(jié)果為：

以上就是詳解Java雙軸快速排序算法的詳細(xì)內(nèi)容，更多關(guān)于Java 雙軸快速排序算法的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！