什么是快速排序？

摘自漫畫算法：

同冒泡排序一樣按咒，快速排序也屬于交換排序挖帘，通過元素之間的比較和交換位置來達(dá)到排序的目的。

不同的是羹膳，冒泡排序在每一輪中只把1個(gè)元素冒泡到數(shù)列的一端睡互，而快速排序則在每一輪挑選一個(gè)基準(zhǔn)元素，并讓其他比它大的元素移動(dòng)到數(shù)列的一端陵像，比它小的元素移動(dòng)到數(shù)列的另一端就珠，從而把數(shù)列拆解成兩個(gè)部分。

快速排序1.png

這種思路就叫做分治法醒颖。

每次把數(shù)列分成兩部分妻怎，究竟有什么好處呢？

假如給出一個(gè)8個(gè)元素的數(shù)列泞歉，一般情況下逼侦，使用冒泡排序需要比較7輪，每一輪把1個(gè)元素移動(dòng)到數(shù)列的一端腰耙，時(shí)間復(fù)雜度為O(n2)榛丢。

而快速排序的流程是什么樣子呢？

快速排序2.png

如上圖所示挺庞，在分治法的思想下晰赞，原數(shù)列的每一輪都被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，知道不可再分為止掖鱼。

每一輪的比較和交換然走，需要把數(shù)組全部元素都遍歷一遍，時(shí)間復(fù)雜度為O(n)戏挡。這樣的遍歷一共需要多少輪呢芍瑞？假如元素個(gè)數(shù)是n，那么平均情況下需要logn輪褐墅，因此快速排序算法總體的平均時(shí)間復(fù)雜度為O(nlogn)拆檬。

基準(zhǔn)元素的選擇

快速排序—基準(zhǔn)元素的選擇2.png

基準(zhǔn)元素，英文是pivot掌栅，在分治過程中秩仆，以基準(zhǔn)元素為中心晌缘，把其他元素移動(dòng)到它的左右兩邊齐莲。

那么如何選擇基準(zhǔn)元素呢岳枷？

最簡(jiǎn)單的方式是選擇數(shù)列的第一個(gè)元素。

快速排序—基準(zhǔn)元素的選擇1.png

這種選擇在絕大多數(shù)情況下是沒有問題的傲诵。但是假如有一個(gè)原本逆序的數(shù)列，期望排序成順序數(shù)列座泳，那么會(huì)出現(xiàn)什么情況呢？

快速排序—基準(zhǔn)元素的選擇2.png

如上圖所示赏陵，整個(gè)數(shù)列并沒有被分成兩個(gè)部分，每一輪都只確定了基準(zhǔn)元素的位置。在這種情況下，數(shù)列的第1個(gè)元素；要么是最小值，要么是最大值，根本無法發(fā)揮分治法的優(yōu)勢(shì)。在這種極端的情況下，快速排序需要進(jìn)行n輪，時(shí)間復(fù)雜度退化成了O(n2)。

那么，該怎么避免這種情況發(fā)生呢？

其實(shí)很簡(jiǎn)單剧防，我們可以隨機(jī)選擇一個(gè)元素作為基準(zhǔn)元素鸡挠，并且讓基準(zhǔn)元素和數(shù)列首元素交換位置。

快速排序—基準(zhǔn)元素的選擇3.png

這樣一來瞎惫，即使在數(shù)列完全逆序的情況下，也可以有效地將數(shù)列分成兩部分挺益。

當(dāng)然伞辛，即使是隨機(jī)選擇基準(zhǔn)元素捏境，也會(huì)有極小的幾率選到數(shù)列的最大值或最小值，同樣會(huì)影響分治的效果倾剿。

所以骏掀，雖然快速排序的平均時(shí)間復(fù)雜度是O(nlogn)笑陈，但最壞情況下的時(shí)間復(fù)雜度是O(n2)际度。

在后文中，為了簡(jiǎn)化步驟涵妥，省去了隨機(jī)選擇基準(zhǔn)元素的過程乖菱，直接把首元素作為基準(zhǔn)元素。

快速排序的實(shí)現(xiàn)

遞歸實(shí)現(xiàn)

選定了基準(zhǔn)元素以后蓬网，我們要做的就是把其他元素中小于基準(zhǔn)元素的都交換到基準(zhǔn)元素一邊窒所，大于基準(zhǔn)元素的都交換到基準(zhǔn)元素的另一邊。

具體如何實(shí)現(xiàn)呢帆锋？有兩種方法吵取。

• 雙邊循環(huán)法

  何謂雙邊循環(huán)法？下面來看一看詳細(xì)過程锯厢。

  給出原始數(shù)列如下皮官，要求對(duì)其從小到大進(jìn)行排序。

  元素的交換—雙邊循環(huán)法1.png

  首先实辑，選定基準(zhǔn)元素pivot捺氢，并且設(shè)置兩個(gè)指針left和right，指向數(shù)列的最左和最右兩個(gè)元素剪撬。

  元素的交換—雙邊循環(huán)法2.png

  接下來進(jìn)行第1次循環(huán)摄乒，從right指針開始，讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較残黑。如果大于或等于pivot馍佑，則指針向左移動(dòng)，如果小于pivot梨水，則right指針停止移動(dòng)挤茄，切換到left指針。

  在當(dāng)前數(shù)列中冰木，1小于4穷劈，所以right直接停止移動(dòng)笼恰，換到left指針，進(jìn)行下一步行動(dòng)歇终。

  輪到left指針行動(dòng)社证，讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素進(jìn)行比較。如果小于或等于pivot评凝，則指針向右移動(dòng)追葡，如果大于pivot，則left指針停止移動(dòng)奕短。

  由于left開始指向的是基準(zhǔn)元素宜肉，判斷肯定相等，所以left右移1位翎碑。

  元素的交換—雙邊循環(huán)法3.png

  由于7大于4谬返，left指針在元素7的位置停下。這時(shí)日杈，讓left和right指針?biāo)赶虻脑剡M(jìn)行交換遣铝。

  元素的交換—雙邊循環(huán)法4.png

  接下來，進(jìn)入第2次循環(huán)莉擒，重新切換到right指針酿炸，向左移動(dòng)。right指針先移動(dòng)到8涨冀，8大于4填硕，繼續(xù)左移。由于2小于4鹿鳖，停止在2的位置廷支。

  按照這個(gè)思路，后續(xù)步驟如圖所示：

  元素的交換—雙邊循環(huán)法5.png

  整體代碼如下（使用遞歸的方式）：

  import java.util.Arrays;
  
  /**
   * Create By ZhangBiao
   * 2020/5/22
   */
  public class Sort {
  
      /**
       * 快速排序
       *
       * @param arr
       * @param startIndex
       * @param endIndex
       */
      public static void quickSort(int[] arr, int startIndex, int endIndex) {
          // 遞歸結(jié)束條件：startIndex大于或等于endIndex時(shí)
          if (startIndex >= endIndex) {
              return;
          }
          // 得到基準(zhǔn)元素位置
          int pivotIndex = partition(arr, startIndex, endIndex);
          // 根據(jù)基準(zhǔn)元素栓辜，分成兩部分進(jìn)行遞歸排序
          quickSort(arr, startIndex, pivotIndex - 1);
          quickSort(arr, startIndex + 1, endIndex);
      }
  
      /**
       * 分治法（雙邊循環(huán)法）
       *
       * @param arr        待交換的數(shù)組
       * @param startIndex 起始下標(biāo)
       * @param endIndex   結(jié)束下標(biāo)
       * @return
       */
      private static int partition(int[] arr, int startIndex, int endIndex) {
          // 取第1個(gè)位置（也可以選擇隨機(jī)位置）的元素作為基準(zhǔn)元素
          int pivot = arr[startIndex];
          int left = startIndex;
          int right = endIndex;
          while (left != right) {
              // 控制right指針比較并左移
              while (left < right && arr[right] > pivot) {
                  right--;
              }
              // 控制left指針比較并右移
              while (left < right && arr[left] <= pivot) {
                  left++;
              }
              // 交換left和right指針?biāo)赶虻脑?            if (left < right) {
                  int p = arr[left];
                  arr[left] = arr[right];
                  arr[right] = p;
              }
          }
          // pivot和指針重合點(diǎn)交換
          arr[startIndex] = arr[left];
          arr[left] = pivot;
          return left;
      }
  
      public static void main(String[] args) {
          int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
          quickSort(arr, 0, arr.length - 1);
          System.out.println(Arrays.toString(arr));
      }
  
  }
  

  在上述代碼中恋拍，quickSort方法通過遞歸的方式，實(shí)現(xiàn)了分而治之的思想藕甩。

  partition方法則實(shí)現(xiàn)了元素的交換施敢，讓數(shù)列中的元素依據(jù)自身大小，分別交換到基準(zhǔn)元素的左右兩邊狭莱。在這里僵娃，我們使用的交換方式是雙邊循環(huán)法。

• 單邊循環(huán)法

  雙邊循環(huán)法從數(shù)組的兩邊交替遍歷元素腋妙，雖然更加直觀默怨，但是代碼實(shí)現(xiàn)相對(duì)繁瑣。而單邊循環(huán)法則簡(jiǎn)單的多骤素，只從數(shù)組的一邊對(duì)元素進(jìn)行遍歷和交換匙睹。我們來看一看詳細(xì)過程愚屁。

  給出原始數(shù)列如下，要求對(duì)其從小到大進(jìn)行排序痕檬。

  元素的交換—單邊循環(huán)法1.png

  開始和雙邊循環(huán)法相似霎槐，首先選定基準(zhǔn)元素pivot。同時(shí)梦谜，設(shè)置一個(gè)mark指針指向數(shù)列起始位置丘跌，這個(gè)mark指針代表小于基準(zhǔn)元素的區(qū)域邊界。

  元素的交換—單邊循環(huán)法2.png

  接下來唁桩，從基準(zhǔn)元素的下一個(gè)位置開始遍歷數(shù)組闭树。

  如果遍歷到的元素大于基準(zhǔn)元素，就繼續(xù)往后遍歷荒澡。

  如果遍歷到的元素小于基準(zhǔn)元素报辱，則需要做兩件事：第一，把mark指針右移1位仰猖，因?yàn)樾∮趐ivot的區(qū)域邊界增大了1；第二奈籽，讓最新遍歷到的元素和mark指針?biāo)谖恢玫脑亟粨Q位置饥侵，因?yàn)樽钚卤闅v的元素歸屬于小于pivot的區(qū)域。

  首先遍歷到元素7衣屏，由于7大于4躏升，所以繼續(xù)遍歷。

  元素的交換—單邊循環(huán)法3.png

  接下來遍歷到的元素是3狼忱，由于3小于4膨疏，所以mark指針右移1位。

  元素的交換—單邊循環(huán)法4.png

  隨后钻弄，讓元素3和mark指針?biāo)谖恢玫脑剡M(jìn)行交換佃却，因?yàn)樵?歸屬于小于pivot的區(qū)域。

  元素的交換—單邊循環(huán)法5.png

  按照這個(gè)思路窘俺，繼續(xù)遍歷饲帅，后續(xù)步驟如圖所示：

  元素的交換—單邊循環(huán)法6.png

  整體代碼如下：

  import java.util.Arrays;
  
  /**
   * Create By ZhangBiao
   * 2020/5/22
   */
  public class Sort {
  
      /**
       * 快速排序
       *
       * @param arr
       * @param startIndex
       * @param endIndex
       */
      public static void quickSort(int[] arr, int startIndex, int endIndex) {
          // 遞歸結(jié)束的條件：startIndex >= endIndex
          if (startIndex >= endIndex) {
              return;
          }
          // 得到基準(zhǔn)元素位置
          int pivotIndex = partition(arr, startIndex, endIndex);
          // 根據(jù)基準(zhǔn)元素，分成兩部分進(jìn)行遞歸排序
          quickSort(arr, startIndex, pivotIndex - 1);
          quickSort(arr, pivotIndex + 1, endIndex);
      }
  
      /**
       * 分治法（單邊循環(huán)法）
       *
       * @param arr        待交換的數(shù)組
       * @param startIndex 起始下標(biāo)
       * @param endIndex   結(jié)束下標(biāo)
       * @return
       */
      private static int partition(int[] arr, int startIndex, int endIndex) {
          // 取第1個(gè)位置（也可以選擇隨機(jī)位置）的元素作為基準(zhǔn)元素
          int pivot = arr[startIndex];
          int mark = startIndex;
          for (int i = startIndex + 1; i <= endIndex; i++) {
              if (arr[i] < pivot) {
                  mark++;
                  int p = arr[mark];
                  arr[mark] = arr[i];
                  arr[i] = p;
              }
          }
          arr[startIndex] = arr[mark];
          arr[mark] = pivot;
          return mark;
      }
  
      public static void main(String[] args) {
          int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
          quickSort(arr, 0, arr.length - 1);
          System.out.println(Arrays.toString(arr));
      }
  
  }
  

  可以很明顯的看出瘤泪，partition方法只要一個(gè)大循環(huán)就搞定了灶泵，的確比雙邊循環(huán)法簡(jiǎn)單多了。

非遞歸實(shí)現(xiàn)

注意：絕大多數(shù)的遞歸邏輯对途，都可以用棧的方式來代替赦邻。

為什么這樣說呢？

在方法中一層一層的調(diào)用方法实檀，本身就使用了一個(gè)方法調(diào)用棧惶洲。每次進(jìn)入一個(gè)新方法按声，就相當(dāng)于入棧；每次有方法返回湃鹊，將相當(dāng)于出棧儒喊，所以，可以把原本的遞歸實(shí)現(xiàn)轉(zhuǎn)化成一個(gè)棧的實(shí)現(xiàn)币呵，在棧中存儲(chǔ)每一次方法調(diào)用的參數(shù)怀愧。

整體代碼如下：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Create By ZhangBiao
 * 2020/5/22
 */
public class Sort {

    /**
     * 快速排序
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        // 用一個(gè)集合棧來代替遞歸的函數(shù)棧
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();
        // 整個(gè)數(shù)列的起止下標(biāo)，以哈希的形式入棧
        HashMap<String, Integer> rootParam = new HashMap<>();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);
        // 循環(huán)結(jié)束條件：棧為空時(shí)
        while (!quickSortStack.isEmpty()) {
            // 棧頂元素出棧余赢，得到起止下標(biāo)
            Map<String, Integer> param = quickSortStack.pop();
            // 得到基準(zhǔn)元素位置
            int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
            //根據(jù)基準(zhǔn)元素分成兩部分芯义，把每一部分的起止下標(biāo)入棧
            if (param.get("startIndex") < pivotIndex - 1) {
                HashMap<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivotIndex - 1);
                quickSortStack.push(leftParam);
            }
            if (pivotIndex + 1 < param.get("endIndex")) {
                HashMap<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }

    /**
     * 分治法（單邊循環(huán)法）
     *
     * @param arr        待交換的數(shù)組
     * @param startIndex 起始下標(biāo)
     * @param endIndex   結(jié)束下標(biāo)
     * @return
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第1個(gè)位置（也可以選擇隨機(jī)位置）的元素作為基準(zhǔn)元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}

和遞歸實(shí)現(xiàn)相比，非遞歸方式代碼的變動(dòng)只發(fā)生在quickSort方法中妻柒。該方法引入了一個(gè)存儲(chǔ)Map類型元素的棧扛拨，用于存儲(chǔ)每一次交換時(shí)的起始下標(biāo)和結(jié)束下標(biāo)。
每一次循環(huán)举塔，都會(huì)讓棧頂元素出棧绑警，通過partition方法進(jìn)行分治，并且按照基準(zhǔn)元素的位置分成左右兩部分央渣，左右兩部分再分別入棧计盒。當(dāng)棧為空時(shí)，說明排序已經(jīng)完畢芽丹，退出循環(huán)北启。