詳解Java雙軸快速排序算法
首選，雙軸快排也是一種快排的優化方案，在JDK的Arrays.sort()中被主要使用。所以，掌握快排已經不能夠滿足我們的需求，我們還要學會雙軸快排的原理和實現才行。
二、回顧單軸快排單軸快排也就是我們常說的普通快速排序，對于快速排序我想大家應該都很熟悉：基于遞歸和分治的，時間復雜度最壞而O(n2),最好和平均情況為O(nlogn).
而快排的具體思路也很簡單，每次在待排序序列中找一個數(通常最左側多一點)，然后在這個序列中將比他小的放它左側，比它大的放它右側。
如果運氣肯不好遇到O(n)平方的，那確實就很被啦：
實現起來也很容易，這里直接貼代碼啦：
private static void quicksort(int [] a,int left,int right){ int low=left; int high=right; //下面兩句的順序一定不能混，否則會產生數組越界！！！very important！！！ if(low>high)//作為判斷是否截止條件 return; int k=a[low];//額外空間k，取最左側的一個作為衡量，最后要求左側都比它小，右側都比它大。 while(low<high)//這一輪要求把左側小于a[low],右側大于a[low]。 { while(low<high&&a[high]>=k)//右側找到第一個小于k的停止 { high--; } //這樣就找到第一個比它小的了 a[low]=a[high];//放到low位置 while(low<high&&a[low]<=k)//在low往右找到第一個大于k的，放到右側a[high]位置 { low++; } a[high]=a[low]; } a[low]=k;//賦值然后左右遞歸分治求之 quicksort(a, left, low-1); quicksort(a, low+1, right);}三、雙軸快排分析
咱們今天的主題是雙軸快排，雙軸和單軸的區別你也可以知道，多一個軸，前面講了快排很多時候選最左側元素以這個元素為軸將數據劃分為兩個區域，遞歸分治的去進行排序。但單軸很多時候可能會遇到較差的情況就是當前元素可能是最大的或者最小的，這樣子元素就沒有被劃分區間，快排的遞推T(n)=T(n-1)+O(n)從而為O(n2).
雙軸就是選取兩個主元素理想將區間劃為3部分，這樣不僅每次能夠確定元素個數增多為2個，劃分的區間由原來的兩個變成三個，最壞最壞的情況就是左右同大小并且都是最大或者最小，但這樣的概率相比一個最大或者最小還是低很多很多，所以雙軸快排的優化力度還是挺大的。
3.1、總體情況分析至于雙軸快排具體是如何工作的呢？其實也不難理解，這里通過一系列圖講解雙軸快排的執行流程。
首先在初始的情況我們是選取待排序區間內最左側、最右側的兩個數值作為pivot1和pivot2 .作為兩個軸的存在。同時我們會提前處理數組最左側和最右側的數據會比較將最小的放在左側。所以pivot1<pivot2.
而當前這一輪的最終目標是，比privot1小的在privot1左側，比privot2大的在privot2右側，在privot1和privot2之間的在中間。
這樣進行一次后遞歸的進行下一次雙軸快排，一直到結束，但是在這個執行過程應該去如何處理分析呢？需要幾個參數呢？
假設知道排序區間[start，end]。數組為arr， pivot1=arr[start],pivot2=arr[end] 還需要三個參數left，right和k。 l left初始為start，[start,left]區域即為小于等于pivot1小的區域(第一個等于)。 right與left對應，初始為end，[right,end]為大于等于pivot2的區域(最后一個等于)。 k初始為start+1，是一個從左往右遍歷的指針，遍歷的數值與pivot1，pivot2比較進行適當交換，當k>=right即可停止。
然后你可能會問k遍歷時候究竟怎么去交換？left和right該如何處理呢？不急我帶你慢慢分析，首先K是在left和right中間的，遍歷k的位置和pivot1，pivot2進行比較：
如果arr[k]<pivot1,那么先++left，然后swap(arr,k,left),因為初始在start在這個過程不結束start先不動。然后k++；繼續進行
而如果arr[k]>pivot2.(區間自行安排即可)有點區別的就是right可能連續的大于arr[k],比如9 3 3 9 7如果我們需要跳過7前面9到3才能正常交換，這和快排的交換思想一致，當然再具體的實現上就是right--到一個合適比arr[k]小的位置。然后swap(arr,k,right)切記此時k不能自加。因為帶交換的那個有可能比pivot1還小要和left交換。
如果是介于兩者之間，k++即可
3.3、收尾工作在執行完這一趟即k=right之后，即開始需要將pivot1和pivot2的數值進行交換
swap(arr, start, left);swap(arr, end, right);
然后三個區間根據編號遞歸執行排序函數即可。
四、雙軸快排代碼在這里，分享下個人實現雙軸快排的代碼：
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;//參數不對直接返回if(arr[start]>arr[end]) swap(arr, start, end);int pivot1=arr[start],pivot2=arr[end];//儲存最左側和最右側的值//(start，left]:左側小于等于pivot1 [right,end)大于pivot2int left=start,right=end,k=left+1;while (k<right) { //和左側交換 if(arr[k]<=pivot1) {//需要交換swap(arr, ++left, k++); } else if (arr[k]<=pivot2) {//在中間的情況k++; } else {while (arr[right]>=pivot2) {//如果全部小于直接跳出外層循環 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; }}
執行結果為：
以上就是詳解Java雙軸快速排序算法的詳細內容，更多關于Java 雙軸快速排序算法的資料請關注好吧啦網其它相關文章！
相關文章：
網公網安備