快速排序

快速排序

快速排序是對冒泡排序的改進，冒泡排序的缺陷就是一輪走完雖然也做了大量的交換，但是剩下的數據之間沒有關系下一次還要再重新找一個最大的。而快速排序對它的改進是，一輪走完不會找到最大的值，而是采用了分治思想將數分為左小右大的兩部分。然后這兩部分再遞歸的進行這種輪，最終慢慢趨于有序。

快速排序.gif

基本思想

老韓思想

選取一個基準值，然后將所有的數據分為左右兩部分，左邊小于等于基準值，右邊大于基準值。注意點，基準值是取出來做一個參照的，遍歷的時候還是遍歷整個數據集的，而不會跳過這個挑出來的基準值。額，感覺還是看看代碼然后debug吧。

算法導論思想

這個就比較好理解了，接收參數quickSort(arr,p,r),arr就是需要排序的那個數組，arr = [p,.....,r],p和r就是這個數組的開始和結束索引。arr[r]也就是最后一個元素作為基準。然后設一個i等于p-1，這i就是指向小的那部分的最后一個的下標，由于一開始還沒有所以指向p-1,就是表示溢出。開始循環(huán)for j = p to r - 1，這個意思就是循環(huán)p到r-1，要將它們處理分到小部分還是大部分,取出的那個下標用j來保存。每個j對應的數據取出來之后，如果它的值小于等于基準，那么就放入到小部分，大于基準就放入大部分。

需要知道以下,k是任意一個下標

  • p<=k<=i表示小于等于基準那部分
  • i<k<j那部分表示大于基準的部分
  • j<k<r那部分表示還沒有處理的隨機部分
  • k == r是基準，基準是不需要處理（分部分）的

最終,j == r的時候分好部分了，最后將基準和大部分的第一個值進行交換就能夠完成一輪處理，然后可以進行遞歸。進行快排的元素小于等于1的時候就完成了排序。

代碼實現

這里有兩種實現思想

尚硅谷老韓

package _6_sort;
import java.util.Arrays;
import java.util.Date;
public class QuickSort {
    public static void quickSort(int[] data, int left, int right) {
        //取第一個數作為基準，基準隨便選一個都可以的
        int pivot = data[left], l = left, r = right;
        int temp;
        while (l < r) {
            //找到左邊一個大于等于基準的
            // 如果沒有這個等于，可能基準就是最大值的話，
            // 然后找不到了(會一直找下去)，還需要加一個限制不讓下標溢出
            while (data[l] < pivot) l++;
            //找到右邊一個小于等于基準的
            while (data[r] > pivot) r--;
            if (r <= l)
                //已經分好了，就兩種情況，一：兩邊都找到了基準(說明基準左邊都是小于等于基準的，右邊都是大于等于基準的)
                // ，二：已經分好了
                break;
            //交換
            temp = data[r];
            data[r] = data[l];
            data[l] = temp;
            //注意：雖然兩個都是符合的，而且不需要下次再試的了，但是如果兩個同時移位的話，會出現問題，
            //就是比如說現在基準是4，l指向2，r指向了4，他們中間有個3，如果兩個同時進行移位的話就出現
            //l、r同時指向一個不是基準的值，這樣下面進行處理的時候就不能又兩個同時移動了，也就是出現了兩種情況
            //就又得if-else進行判斷然后分別處理了，還得判斷這個不是基準的值到底小于基準還是大于基準（麻煩）
            if (data[l] == pivot) r--;
            if (data[r] == pivot) l++;
            //為什么data[l] == pivot卻要移動r,也就是為什么移動不是pivot那個值呢？
            //這也是為了想要等于跳出這個循環(huán)必須由上面的if來完成，保障等于的時候一定指向pivot
            //如果此時現在基準是4，l指向一個2，r指向一個4然后他們兩個是挨著的，那移動了r的話
            //就直接l==r出去了，然后此時data[r]等于2，經過下面的處理必然又出錯了

        }
        //如果此時r==l(此時這個位置肯定等于基準值，這個位置不需要再排序了，值是處于中間位置的)，
        // 那么需要進行移位，不然遞歸的時候會出現兩個部分重合的情況
        if (r == l) {
            r--;
            l++;
        }
        if (left < r) {//如果這一部分小于等于1的話就不用再遞歸了，直接是有序的
            quickSort(data, left, r);
        }
        if (right > l) {
            quickSort(data, l, right);
        }
    }
//測試代碼
    public static void main(String[] args) {
//        int[] arr = RandomProducer.produceRandom(-500, 100000000, 8000000);
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 8, 9, 1, 7, 2, 3, 5, 4, 8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
        Date from = new Date();
        quickSort(arr, 0, arr.length - 1);
//        ShiftShellSort(arr);
//        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
        System.out.println("運行了" + (new Date().getTime() - from.getTime()) + "毫秒");
    }
}

算法導論第三版實現方式

package _6_sort.AlgorithmBooks;

import _6_sort.RandomProducer;

import java.util.Arrays;
import java.util.Date;

/**
 * author waigo
 * create 2021-01-28 11:31
 */
public class QuickSort {
    //partition(A,p,r)，這個方法用來分開那個區(qū)域
    //quickSort(A,p,r),處理區(qū)域[p,...,r] E A
    public static int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                i++;
                exchange(A, i, j);
            }
        }
        exchange(A, i + 1, r);
        return i + 1;
    }

    public static void exchange(int[] A, int aIndex, int bIndex) {
        if(aIndex!=bIndex){
            int temp = A[aIndex];
            A[aIndex] = A[bIndex];
            A[bIndex] = temp;
        }
    }

    //A = [p,....,r]
    public static void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = partition(A, p, r);
            quickSort(A, p, q - 1);
            quickSort(A, q + 1, r);
        }
    }
//測試代碼
    public static void main(String[] args) {
        int[] arr = RandomProducer.produceRandom(-500, 100000000, 8000000);
//        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
        Date from = new Date();
        quickSort(arr, 0, arr.length - 1);
//        ShiftShellSort(arr);
//        System.out.println("排序后");
//        System.out.println(Arrays.toString(arr));
        System.out.println("運行了" + (new Date().getTime() - from.getTime()) + "毫秒");
    }
}

可以看出，算法導論這種實現方式的好處是不需要考慮那么多條件，只要循環(huán)不變量設置好，后面就只要處理判斷分邊的問題了。經過測試，雖然實現的方式不同，但是由于算法的思想內核是相同的，所以這兩種方式的速度不相伯仲。而快排比起希爾來說真的是又上了一個檔次，我的電腦測試800,0000條數據的排序才用了1200ms左右。而移位式希爾排序800,0000條數據需要差不多2500ms。

不愧是快速排序，還真是名不虛傳。不過我們這個一次只能處理完一個就是那個pivot，而和pivot相同的還得走下面的流程再次遞歸，所以可以改良。

上面講的就是1.0版的快排，核心是"01partition"的操作，下面來介紹一個新玩意兒，荷蘭國旗問題，就是將一個數組分為三塊，左邊小于pivot,中間等于pivot，右邊大于pivot，這就是升級版的partition.


荷蘭國旗.png

思想：還和partition一樣整一個指針smallTop指向最小區(qū)的頭，不過現在需要一個指針指向最大區(qū)的頭bigLow，我們這里的pivot就取最后一個值，所以最大區(qū)的頭一開始指向最后一個位置，若是pivot從外面?zhèn)鬟M來就可以指向r+1(r指的是處理區(qū)域的最右邊)位置，要靈活一點。然后一個指針j從p位置(處理區(qū)域開始位置)開始遍歷，若是小于pivot則進入小于區(qū)(j指針后移)，等于pivot就直接后移，大于的時候需要注意，由于從大于區(qū)換下來的元素是還沒看過的，所以要停在原地繼續(xù)看這個新換來的。這里的循環(huán)結束條件和partition可不同，不能再設置為j<r了，因為是兩邊往中間擠，所以要是j==bigLow的時候就說明已經分好區(qū)了，[p...smallTop]<pivot,[smallTop+1...j-1]==pivot,[bigLow...r]>pivot。嗯，由于我們這里設置r位置為pivot，所以swap(bigLow++,r);

show you my code.

/**
 * @param arr 待處理的數組
 * @param p 處理區(qū)域[p...r]
 * @param r
 * @return 下標0:小于x的top 下標1：大于x的low
 * 經過荷蘭國旗處理，[p...smallTop] 小于x，[smallTop+1...bigLow-1]等于x，[bigLow...r]大于0
 */
public static int[] netherlangsFlag(int[] arr, int p, int r) {
    int smallTop = p - 1, bigLow = r;
    int j = p, pivot = arr[r];
    while (j < bigLow) {
        if (arr[j] < pivot) swap(arr, ++smallTop, j);
        else if (arr[j] > pivot) swap(arr, --bigLow, j--);//這個bigLow位置的元素還沒看過，所以j需要留在原地再看一遍
        j++;//等于的時候直接移動j不用進行交換操作
    }
    swap(arr, bigLow++, r);
    return new int[]{smallTop, bigLow};
}

利用荷蘭國旗操作升級快排2.0

/**
 * quickSort2.0版本,使用荷蘭國旗操作進行優(yōu)化，一次將等于x的全部搞定
 * @param arr
*/
public static void quickSort2(int[] arr) {
    process2(arr, 0, arr.length - 1);
}
public static void process2(int[] arr, int p, int r) {
    if (p < r) {
        int[] flag = netherlangsFlag(arr, p, r);
        int smallTop = flag[0], bigLow = flag[1];
        process2(arr, p, smallTop);
        process2(arr, bigLow, r);
    }
}

升級點，一次解決了等于pivot的一堆數據。這就是最經典的快排。

不過上面兩個算法其實是O(N2)的算法，注意算法的時間復雜度是按最差情況來算的，假設一個算法直接就是有序的然后進行快排，那么每次處理完成的都是最后一個，然后剩下全部進入下一輪處理，這個時間復雜度就是O(N2)，那么升級點就是讓它不要每次都只是處理最后一個，而是隨機挑一個位置做pivot，這好處就是下一輪兩邊可能數量是比較均衡的，這樣就減少了遞歸的次數。

額，你可能會說了，既然算法按照最差情況來估時間復雜度，那最差情況能不能就是每次隨機找到的都是最后一個。這里還得解釋一下，這個最差情況說的是同一批數據進行處理時流程是固定的，就是像1.0和2.0版本，不管你怎么試都會是最后一個做pivot。但是3.0版本這個隨機pivot是隨機生成的，你無法保證會出現在哪里，所以最差情況就不能說它全生成在r位置。經過研究，隨機快排也就是快排3.0，時間復雜度為O(N*logN),空間復雜度為O(logN)

2.0-->3.0,show you my code.

其實其他和2.0都一樣，就加一個隨機pivot選擇

public static void process3(int[] arr, int p, int r) {
    if (p < r) {
        //(int) (Math.random() * (r - p + 1)) --> [0,r-p] + p -->[p,r]
        int pivotIdx = (int) (Math.random() * (r - p + 1)) + p;//[p,r]，+p別忘了，偏移量
        swap(arr, pivotIdx, r);//x放在r位置
        int[] flags = netherlangsFlag(arr, p, r);
        process3(arr, p, flags[0]);
        process3(arr, flags[1], r);
    }
}
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容