詳解Java雙軸快速排序算法

更新時間：2021年06月16日 11:50:41 作者：bigsai

在排序算法中，快速排序是占比非常多的一環(huán)，但是快速排序其思想一直被考察研究，也有很多的優(yōu)化方案。這里主要講解雙軸快速排序的思想和實現(xiàn)

一、前言

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

二、回顧單軸快排

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

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

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

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

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

三、雙軸快排分析

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

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

3.1、總體情況分析

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

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

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

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

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

3.2、k交換過程

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

如果arr[k]<pivot1,那么先++left，然后swap(arr,k,left),因為初始在start在這個過程不結(jié)束start先不動。然后k++；繼續(xù)進行

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

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

3.3、收尾工作

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

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

然后三個區(qū)間根據(jù)編號遞歸執(zhí)行排序函數(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ù)不對直接返回
        if(arr[start]>arr[end])
            swap(arr, start, end);
        int pivot1=arr[start],pivot2=arr[end];//儲存最左側(cè)和最右側(cè)的值
        //(start，left]:左側(cè)小于等于pivot1 [right,end)大于pivot2
        int 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é)果為：