詳解Java雙軸快速排序算法

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

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

一、前言

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

二、回顧單軸快排

單軸快排也就是我們常說(shuō)的普通快速排序，對(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)起來(lái)也很容易，這里直接貼代碼啦：

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)前元素可能是最大的或者最小的，這樣子元素就沒(méi)有被劃分區(qū)間，快排的遞推T(n)=T(n-1)+O(n)從而為O(n2).

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

3.1、總體情況分析

至于雙軸快排具體是如何工作的呢？其實(shí)也不難理解，這里通過(guò)一系列圖講解雙軸快排的執(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í)行過(guò)程應(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交換過(guò)程

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

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

而如果arr[k]>pivot2.(區(qū)間自行安排即可)有點(diǎn)區(qū)別的就是right可能連續(xù)的大于arr[k],比如9 3 3 9 7如果我們需要跳過(guò)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之后，即開(kāi)始需要將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)大于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é)果為：