快速排序的實(shí)現(xiàn)細(xì)節(jié)，你真的懂了？

前言

這么多排序算法里面，我最喜歡考快速排序，也是我出去面試時(shí)被問到最多的，快速排序代碼量適中，并且考察你設(shè)計(jì)函數(shù)和遞歸的能力，是非常適合用來面試的。

如果你還不明白快速排序的思路，可以看下上面的圖，快速排序核心思想就是找到一個(gè)點(diǎn)，然后通過交換，讓點(diǎn)左邊的數(shù)都小于等于這個(gè)點(diǎn)的值，點(diǎn)右邊的數(shù)都大于等于這個(gè)點(diǎn)的值，再在左右進(jìn)行遞歸。

核心思想雖然一致，但是快速排序的寫法還是很多的，這篇文章來介紹幾種。

框架

首先我們明確命名，在快速排序中，我們找到的這個(gè)點(diǎn)一般叫做pivot，中文叫支點(diǎn)或者叫樞軸。我個(gè)人在考察別人代碼的時(shí)候，命名是非常重要的考察點(diǎn)，我自己寫代碼也非常注重命名，也希望大家能夠重視起來。

接下來我們來規(guī)劃一下快排中需要哪些函數(shù)。首先swap最好還是抽成一個(gè)函數(shù)，就用來交換數(shù)組中的兩個(gè)數(shù)。然后因?yàn)橐f歸，我們需要一個(gè)innerQuickSort(int[] arr, int start, int end)，用來進(jìn)行從start到end的一個(gè)排序，最后我們需要一個(gè)innerFindPivot(int[] arr, int start, int end)，用于在start和end間找到一個(gè)pivot，并且使得pivot左邊的數(shù)都小于等于pivot，右邊的數(shù)都大于等于pivot。

接下來我們來看一下大體框架。

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static int innerFindPivot(int[] arr, int start, int end) {
    // TODO
}

public static void innerQuickSort(int[] arr, int start, int end) {
    int pivot = innerFindPivot(arr, start, end);
    if(start < pivot - 1) {
        innerQuickSort(arr, start, pivot - 1);
    }
    if(pivot + 1 < end) {
        innerQuickSort(arr, pivot + 1, end);
    }
}

public static void quickSort(int[] arr) {
    innerQuickSort(arr, 0, arr.length - 1);
}

真正的函數(shù)quickSort直接調(diào)用innerQuickSort，而innerQuickSort調(diào)用innerFindPivot找到pivot后，遞歸地調(diào)用innerQuickSort就能完成排序了。

所以真正核心的地方就是innerFindPivot。

三種方式

我們先看第一種方法，我們先將arr[start]作為pivot，然后處理后面的數(shù)，處理的時(shí)候我們使用雙指針的思想，廢話不多說，看下代碼：

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static int innerFindPivot(int[] arr, int start, int end) {
    int left = start, right = end;
    int pivot = arr[start];
    while(left < right) {
        while(left < right && arr[right] > pivot) {
            right--;
        }
        while(left < right && arr[left] <= pivot) {
            left++;
        }
        if(left < right) {
            swap(arr, left, right);
        }
    }
    swap(arr, start, left);
    return left;
}

public static void innerQuickSort(int[] arr, int start, int end) {
    int pivot = innerFindPivot(arr, start, end);
    if(start < pivot - 1) {
        innerQuickSort(arr, start, pivot - 1);
    }
    if(pivot + 1 < end) {
        innerQuickSort(arr, pivot + 1, end);
    }
}

public static void quickSort(int[] arr) {
    innerQuickSort(arr, 0, arr.length - 1);
}

這個(gè)方法需要注意的細(xì)節(jié)還是比較多的，首先必須先right--，然后再left++，否則會有問題，具體為啥讀者可以自行模擬一下。另外=是在left這邊，最后返回也是返回left。

還有一個(gè)問題是pivot的選擇，可以選第一個(gè)數(shù)，也可以選擇一個(gè)隨機(jī)數(shù)，選擇隨機(jī)數(shù)就先和第一個(gè)數(shù)交換，然后再進(jìn)行后續(xù)流程就行。

還有一種雙邊的方法是可以不用選擇pivot的，我們一起看一下。

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static int innerFindPivot(int[] arr, int start, int end) {
    int left = start, right = end;
    boolean isLeft = true;
    while(left < right) {
        if(arr[left] <= arr[right]) {
            if(isLeft) {
                left++;
            } else {
                right--;
            }
        } else {
            swap(arr, left, right);
            isLeft = !isLeft;
        }
    }
    return left;
}

public static void innerQuickSort(int[] arr, int start, int end) {
    int pivot = innerFindPivot(arr, start, end);
    if(start < pivot - 1) {
        innerQuickSort(arr, start, pivot - 1);
    }
    if(pivot + 1 < end) {
        innerQuickSort(arr, pivot + 1, end);
    }
}

public static void quickSort(int[] arr) {
    innerQuickSort(arr, 0, arr.length - 1);
}

這種是雙邊交換之后自動(dòng)產(chǎn)生pivot的位置，不過你仔細(xì)模擬一下會發(fā)現(xiàn)，它其實(shí)也是選擇了最后一個(gè)元素作為pivot，但是這種方法細(xì)節(jié)就少多了，而且left和right是對稱的，所以我更喜歡這種方法。

還有一種單邊的方法，也一起看一下，這種單邊的方法相對雙邊會更簡單一些。

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static int innerFindPivot(int[] arr, int start, int end) {
    int mark = start;
    int pivot = arr[start];
    for(int i = start + 1; i <= end; i++) {
        if(arr[i] < pivot) {
            mark++;
            swap(arr, mark, i);
        }
    }
    swap(arr, start, mark);
    return mark;
}

public static void innerQuickSort(int[] arr, int start, int end) {
    int pivot = innerFindPivot(arr, start, end);
    if(start < pivot - 1) {
        innerQuickSort(arr, start, pivot - 1);
    }
    if(pivot + 1 < end) {
        innerQuickSort(arr, pivot + 1, end);
    }
}

public static void quickSort(int[] arr) {
    innerQuickSort(arr, 0, arr.length - 1);
}

單邊的思想就是保證mark的位置就是pivot的位置，這里也要注意一下，首先i一直是>=mark的，其次mark的位置是小于pivot的數(shù)的邊界。

關(guān)于快排大家還是要細(xì)細(xì)體會，如果還沒理解的話自己畫圖模擬一下，實(shí)在不行背也要背下來，我建議大家至少要能夠手寫其中一種方法。

練習(xí)題

學(xué)習(xí)完快速排序，大家可以去做一下以下的習(xí)題：

leetcode912?排序數(shù)組

leetcode147?鏈表排序