亚洲成色乱码精品一区,国产亚洲日韩中文字幕

算法描述

像歸并排序一樣，快速排序也是一種分治的遞歸算法。經(jīng)典快速排序，輸入存放在數(shù)組里，且算法不產(chǎn)生額外的數(shù)組。將數(shù)組S排序的基本算法由下列簡(jiǎn)單的四步組成：

如果數(shù)組S中的元素個(gè)數(shù)是0或者1，則返回。
取S中任意一元素v，稱之為樞紐元（pivot）。
將 $S-\left \{ v \right \}$ （S中其余元素）劃分成兩個(gè)不相交的集合： $S1=\left \{ x\in S-\left \{ v \right \} |x\leqslant v\right \}$ 和 $S2=\left \{ x\in S-\left \{ v \right \} |x\geqslant v\right \}$ 。
依次返回 $quicksort(S1)$ ， $v$ ， $quicksort(S2)$
步驟的示意圖如下：

快速排序的各步驟

選取樞紐元
這里介紹三種方法。
I. 一種常見但不好的方法
通常的、無知的選擇是將第一個(gè)元素用作樞紐元。如果待排數(shù)組的元素是隨機(jī)的，那么可以接受，而如果輸入時(shí)預(yù)排序的或是反序的，那么這樣的樞紐元會(huì)產(chǎn)生一個(gè)劣質(zhì)的分割，即所有的元素要么被劃入S1，要么被劃入S2.更糟糕的是這種情況毫無例外的會(huì)發(fā)生在所有的遞歸中。這種最壞情形下的性能為O(N2) 。
II. 一種安全的做法
隨機(jī)選取樞紐元。這種方法是安全的，因?yàn)殡S機(jī)的樞紐元不可能接連不斷的產(chǎn)生劣質(zhì)的分割。另一方面，隨機(jī)數(shù)的生成開銷一般很大，根本減少不了算法其余部分的平均運(yùn)行時(shí)間
III.三數(shù)中值分割法（Median-of-Three Partitioning）
一般的做法是使用左端、右端、和中心位置上的三個(gè)元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的壞情況，并且實(shí)際減少了14%的比較次數(shù)。
分割策略
在分割階段要做的就是把所有嚴(yán)格小于樞紐元的元素移到數(shù)組的左邊，而把所有嚴(yán)格大于樞紐元的元素移到數(shù)組的右邊，如果數(shù)組中有其他與樞紐元相等的元素，可保持位置不變即可。每一趟分割之后，樞紐元都會(huì)處在正確的位置上。示意圖如下：

首先將樞紐元與最后位置的元素交換。然后i從第一個(gè)元素開始向后遍歷，j從最后一個(gè)元素開始向前遍歷（i先遍歷，j再遍歷）。當(dāng)i在j的左邊時(shí)，我們將i右移，移過那些小于等于樞紐元的元素；并將j右移，移過那些大于等于樞紐元的元素。當(dāng)i和j停止時(shí)，如果i在j的左邊，那么將這兩個(gè)元素交換，其效果就是將一個(gè)大元素推向右邊，而把一個(gè)小元素推向左邊。當(dāng)i和j相遇時(shí)，停止移動(dòng)，此時(shí)相遇的位置就是樞紐元在數(shù)組中的正確位置，所以最后將樞紐元與相遇位置上的元素進(jìn)行交換。
解釋一下為什么首先將樞紐元與最后位置的元素交換：因?yàn)閕先于j遍歷的緣故，最后i和j相遇的位置上的元素，一定是大于樞紐元的（無論是i遇上j，還是j遇上i）。而大于樞紐元的元素應(yīng)該落在數(shù)組的右邊，所以我們先將樞紐元提前放置在了最后。
同理可得，如果j先于i遍歷，那么最后相遇的位置上的元素必定比樞紐元小，那么這種情況下就不需要提前將樞紐元與最后位置的元素交換了。

代碼

選取第一個(gè)元素作為樞紐元的代碼如下，其中需要注意的點(diǎn)是比較nums[i]或者nums[j]與pivot的大小時(shí)，必須加上等號(hào)，否則當(dāng)nums[i]=nums[j]=pivot時(shí)，i++和j--永遠(yuǎn)無法執(zhí)行到，導(dǎo)致程序就會(huì)陷入無限循環(huán)，跳不出for(;;)。

    public void quickSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }

        // 選取第一個(gè)數(shù)作為樞紐元(若選取最后一個(gè)數(shù)作為樞紐元,就不需要交換位置）
        int pivot = nums[left];
        swapReferences(nums, left, right);

        // j必須從right開始, 保證了當(dāng)樞紐元是最大的數(shù)時(shí)的正確性
        int i = left, j = right;

        while (true) {
            // <= 保證當(dāng) nums[i] = nums[j] = pivot時(shí), 程序不會(huì)陷入無限循環(huán)
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swapReferences(nums, i, j);
            } else {
                break;
            }
        }

        // restore pivot
        swapReferences(nums, i, right);

        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

通過三數(shù)中值分割法的程序如下：

    public void quickSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }

        int pivot = median3(nums, left, right);

        int i = left, j = right - 1;

        while (true) {
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swapReferences(nums, i, j);
            } else {
                break;
            }
        }

        // restore pivot
        swapReferences(nums, i, right - 1);

        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

    /**
     * 三數(shù)中值分割法選取樞紐元(pivot):
     * 對(duì)left, center, right三個(gè)位置的數(shù)進(jìn)行排序, 樞紐元選取center位置的數(shù)
     * 并且將樞紐元放在right-1位置, 這樣只需排序(left, right-1)區(qū)間的數(shù)
     */
    private static int median3(int[] nums, int left, int right) {

        // 將left, center, right三個(gè)元素排序
        int center = (left + right) / 2;
        if (nums[center] < nums[left]) {
            swapReferences(nums, left, center);
        }
        if (nums[right] < nums[left]) {
            swapReferences(nums, left, right);
        }
        if (nums[right] < nums[center]) {
            swapReferences(nums, center, right);
        }

        // 選取center元素作為樞紐元(pivot), 并將樞紐元放置在right-1位置
        swapReferences(nums, center, right - 1);
        return nums[right - 1];
    }

算法分析

正如歸并排序那樣，快速排序也是遞歸的，因此它的分析需要求解一個(gè)遞推公式。快速排序的運(yùn)行時(shí)間等于兩個(gè)遞歸調(diào)用的時(shí)間加上花費(fèi)在分割上的線性時(shí)間。我們得到基本的時(shí)間復(fù)雜度遞推關(guān)系式 $T(N)=T(i)+T(N-i-1)+cN$ 其中i是S1集合中的元素的個(gè)數(shù)。我們將考察三種情況。

最壞情況的分析
樞紐元始終是最小元素。此時(shí) $i=0$ ，我們忽略無關(guān)緊要的 $T(0)=1$ ，那么遞推關(guān)系為 $T(N)=T(N-1)+cN,N>1$ ,求解上面的遞推方程（依次用N-1代替N得到眾多方程，然后相加所有方程）可以得到 $T(N)=T(1)+c\sum_{i=2}^{N}i=O(N^{2})$

最好情況的分析
在最好的情況下，樞紐元正好位于中間。為了簡(jiǎn)化數(shù)學(xué)推導(dǎo)，我們假設(shè)兩個(gè)子數(shù)組恰好各為原數(shù)組的一般大小，那么遞推關(guān)系為 $T(N)=2T(N/2)+cN$ ,求解上面的遞推方程(左右兩邊同除N，依次用N/2代替N得到眾多方程，然后相加所有方程)可以得到 $T(N)=cNlogN+N=O(NlogN)$

平均情況的分析
這是最困難的部分。假設(shè) $T(i)$ 和 $T(N-i-1)$ 的平均值為 $\frac{1}{N}\sum_{i=0}^{N-1}T(i)$ ，那么遞推關(guān)系為 $T(N)=\frac{2}{N}\sum_{i=0}^{N-1}T(i)+cN$ ，最后解得（過程略） $T(N)=O(NlogN)$