java怎么實現(xiàn)隨機快速排序

本文小編為大家詳細介紹“java怎么實現(xiàn)隨機快速排序”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當，希望這篇“java怎么實現(xiàn)隨機快速排序”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

簡介

快速排序也采用的是分而制之的思想。那么快速排序和歸并排序的區(qū)別在什么地方呢？

歸并排序是將所有的元素拆分成一個個排好序的數(shù)組，然后將這些數(shù)組再進行合并。

而快速排序雖然也是拆分，但是拆分之后的操作是從數(shù)組中選出一個中間節(jié)點，然后將數(shù)組分成兩部分。

左邊的部分小于中間節(jié)點，右邊的部分大于中間節(jié)點。

然后再分別處理左邊的數(shù)組合右邊的數(shù)組。

快速排序的例子

假如我們有一個數(shù)組：29,10,14,37,20,25,44,15，怎么對它進行快速排序呢？

先看一個動畫：

我們再分析一下快速排序的步驟。

我們選擇的是最左邊的元素29作為中間點元素，然后將數(shù)組分成三部分：[0, 14, 15, 20, 25],[29],[44, 37]。

中間節(jié)點29已經(jīng)排好序了，不需要處理。

接下來我們再對左右分別進行快速排序。最后就得到了一個所有元素都排序的數(shù)組。

快速排序的java代碼實現(xiàn)

我們先來看最核心的部分partition，如何將數(shù)組以中間節(jié)點為界，分成左右兩部分呢？

我們的最終結(jié)果，是要將array分割成為三部分。

首先我們選擇最左側(cè)的元素作為中間節(jié)點的值。然后遍歷數(shù)組中的其他元素。

假如m=middleIndex，k=要遍歷的元素index

考慮兩種情況，第一種情況是數(shù)組中的元素比中間節(jié)點的值要大。

這種情況下，m不需要移動，k+1繼續(xù)遍歷即可。

第二種情況下，數(shù)組中的元素比中間節(jié)點的值要小。

因為m左邊的元素都要比中間節(jié)點的值要小，所以這種情況下m需要+1，即右移一位。

現(xiàn)在m+1位置的元素要么還沒有進行比較，要么就是比中間節(jié)點的值要大，我們可以巧妙的將m+1位置的元素和k位置的元素互換位置，這樣仍然能夠保證m左側(cè)的元素要比中間節(jié)點的值要小。

將上面的分析總結(jié)成java代碼如下：

 private int partition(int[] array, int i, int j) {
        //選擇最左側(cè)的元素作為中心點,middleValue就是中心點的值
        int middleValue = array[i];
        int middleIndex = i;
        //從i+1遍歷整個數(shù)組
        for (int k = i+1; k <= j; k++) {
            //如果數(shù)組元素小于middleValue，表示middleIndex需要右移一位
            //右移之后，我們需要將小于middleValue的array[k]移動到middleIndex的左邊，
            // 最簡單的辦法就是交換k和middleIndex的值
            if (array[k] < middleValue) {
                middleIndex++;
                //交換數(shù)組的兩個元素
                swap(array, k , middleIndex);
            } //如果數(shù)組元素大于等于middleValue,則繼續(xù)向后遍歷,middleIndex值不變
        }
        // 最后將中心點放入middleIndex位置
        swap(array, i, middleIndex);
        return middleIndex;
    }

最后我們需要將最左側(cè)的元素和中間節(jié)點應(yīng)該在的index的元素互換下位置，這樣就將中間節(jié)點移動到了中間位置，并返回中間位置。

再來看下divide的代碼：

    public void doQuickSort(int[] array, int low, int high) {
        //遞歸的結(jié)束條件
        if (low < high) {
            //找出中心節(jié)點的值
            int middleIndex = partition(array, low, high);
            //數(shù)組分成了三部分：
            // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
            //遞歸遍歷左側(cè)部分
            doQuickSort(array, low, middleIndex-1);
            // a[m] 是中心節(jié)點，已經(jīng)排好序了，不需要繼續(xù)遍歷
            //遞歸遍歷右側(cè)部分
            doQuickSort(array, middleIndex+1, high);
            log.info("QuickSort之后的數(shù)組:{}",array);
        }
    }

divide的代碼就很簡單了，找到中間節(jié)點的位置之后，我們再分別遍歷數(shù)組的左右兩邊即可。最后得到排好序的數(shù)組。

隨機快速排序的java實現(xiàn)

上面的例子中，我們的中間節(jié)點的選擇是數(shù)組的最左元素，為了保證排序的效率，我們可以從數(shù)組中隨機選擇一個元素來作為中間節(jié)點。

 private int partition(int[] array, int i, int j) {
        //隨機選擇一個元素作為中心點,middleValue就是中心點的值
        int randomIndex=i+new Random().nextInt(j-i);
        log.info("randomIndex:{}",randomIndex);
        //首先將randomIndex的值和i互換位置,就可以復(fù)用QuickSort的邏輯
        swap(array, i , randomIndex);
        int middleValue = array[i];
        int middleIndex = i;
        //從i遍歷整個數(shù)組
        for (int k = i+1; k <= j; k++) {
            //如果數(shù)組元素小于middleValue，表示middleIndex需要右移一位
            //右移之后，我們需要將小于middleValue的array[k]移動到middleIndex的左邊，
            // 最簡單的辦法就是交換k和middleIndex的值
            if (array[k] < middleValue) {
                middleIndex++;
                //交換數(shù)組的兩個元素
                swap(array, k , middleIndex);
            } //如果數(shù)組元素大于等于middleValue,則繼續(xù)向后遍歷,middleIndex值不變
        }
        // 最后將中心點放入middleIndex位置
        swap(array, i, middleIndex);
        return middleIndex;
    }

上面的代碼，我們在分區(qū)的時候，先選擇出一個隨機的節(jié)點，然后將這個隨機的節(jié)點和最左側(cè)的元素交換位置，后面的代碼就可以重用上面的QuickSort的代碼邏輯了。

讀到這里，這篇“java怎么實現(xiàn)隨機快速排序”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。