快速排序遞歸方法和非遞歸方法詳解

1、快速排序（遞歸）

1.1、快速排序思想（遞歸）

• 快速排序（遞歸）是對數(shù)組進行拆解，也就是基于分治的思想。這里討論將數(shù)組升序的情況：每次選出一個樞軸，在這部分數(shù)據(jù)中將小于該樞軸的元素放到樞軸的左邊，大于樞軸的元素放到樞軸的右邊，然后基于此次樞軸的位置，分成左右兩個區(qū)間。再繼續(xù)對此左右區(qū)間繼續(xù)進行上述操作。每趟選出一個樞軸，每趟排序都可以將這次排序的樞軸放到最終位置。（看下面圖解）

  • 樞軸：即可以將序列分成兩半的元素，樞軸大于左邊序列，樞軸小于右邊序列。
    

1.2、排序過程（遞歸）圖解

• 每次選出一個樞軸（這里每次選的的最此次需要排序的左邊元素），把這趟要排序的元素中小于樞軸的元素放到樞軸的左邊，大于樞軸的元素放到樞軸的右邊。

  • 也就是right先走（最后left所指元素一定會比keyi所指元素?。瑥挠彝笞?，找到比樞軸小的元素，就停下來。然后再left走，從左往右找，找到比樞軸大的元素，就停下來。然后交此時left和right對應的元素的值。left和right繼續(xù)走，直到left == right。此時left所指元素一定小于keyi所指元素，將left所指元素余keyi所指元素互換，以確定此趟排序一個元素的最終位置pos。

  

• 確定好了樞軸的最終位置后，遞歸調用，把此次要排序的元素分成兩組，左邊一組（小于樞軸），右邊一組（大于樞軸），對此左右兩組繼續(xù)采用上述方法。

  

  

  

  • 這里僅畫了部分圖解，其他的過程自己考慮（和上述過程類似）。

1.3、快速排序（遞歸）代碼

1.3.1、原始方法

• 先寫出一趟排序的代碼，即先選出此趟排序的樞軸，右邊指針right先走，從右往左找到第一個小于樞軸的元素，就停下來。然后左邊指針left再走，從左往右找到第一個大于樞軸的元素，就停下來。交換此時左右指針所指向的元素，然后繼續(xù)上述過程（right先走），直到left == right。排序完將此樞軸放到整個數(shù)組的最終位置上。一趟排序的代碼如下：

  //一趟排序  ---  原始方法
  int PartSort1(int *arr, int left, int right) {
      int midi = GetMid(arr, left, right);
      Swap(&arr[left], &arr[midi]);
      int keyi = left;
      while (left < right) {
          while (left < right && arr[right] >= arr[keyi]) {
              --right;
          }
          while (left < right && arr[left] <= arr[keyi]) {
              ++left;
          }
          Swap(&arr[left], &arr[right]);
      }
      //由于是右邊先走，所以left處為最終樞軸元素的最終位置
      Swap(&arr[keyi], &arr[left]);
      return left;
  }
  

  • 這里我們注意到，這里有個GetMid函數(shù)，這個函數(shù)是干嘛的呢？其實，這個函數(shù)是用來優(yōu)化遞歸版的快速排序的。這個函數(shù)可以用來對每趟排序的樞軸的取值更合理，即每趟取此趟排序的最前元素、最后元素、中間元素的中位數(shù)。這樣可以非常有效防止對于一個基本有序或者已經(jīng)有序的序列進行快速排序的時候遞歸深度太深。GetMid函數(shù)代碼如下：

    //取第一個、中間一個、最后一個元素中的中位數(shù)
    int GetMid(int *arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[mid] >= arr[left]) {
            if (arr[mid] >= arr[right]) {//mid處元素值最大
                if (arr[left] <= arr[right]) {//right處元素值第二大
                    return right;
                } else {
                    return left;//left處元素值第二大
                }
            } else {//right處元素值最大
                return mid;//mid處元素值第二大
            }
        } else {
            if (arr[left] >= arr[right]) {//left處元素值最大
                if (arr[mid] >= arr[right]) {
                    return mid;//mid處元素值第二大
                } else {
                    return right;//right處元素值第二大
                }
            }
        }
    }
    

    下面再介紹兩種上述一趟排序的算法，分別是挖坑法和左右指針法。

1.3.2、挖坑法

• 挖坑法：首先在最左邊樞軸元素處挖坑，用hole標記洞的位置，并且記錄此元素值key，然后right先走，從右往左走，找到比key小的元素將其填補到左邊的坑，并將此元素位置作為新的坑，然后再left走，找到比key大的元素將其填補到右邊的坑，并將此元素位置作為新的坑。重復上述過程，直到left == right，再將已記錄的樞軸填補到left位置上。最后洞的位置就是這趟排序樞軸的最終位置。

  • 挖坑法部分圖解：

    

    

  • 挖坑法代碼：

    //一趟排序  ---  挖坑法
    int PartSort2(int *arr, int left, int right) {
        int midi = GetMid(arr, left, right);
        Swap(&arr[left], &arr[midi]);
        int key = arr[left];
        int hole = left;//左邊第一個坑位
        while (left < right) {
            //右邊先走，找小，填到左邊的坑，在右邊形成新的坑位
            while (left < right && arr[right] >= key) {
                --right;
            }
            //右邊坑位
            arr[hole] = arr[right];
            hole = right;
            //左邊先走，找大，填到右邊的坑，在左邊形成新的坑位
            while (left < right && arr[left] <= key) {
                ++left;
            }
            //左邊坑位
            arr[hole] = arr[left];
            hole = left;
        }
        arr[hole] = key;//最后一次坑填當前樞軸元素
        return hole;
    }
    

1.3.3、左右指針法

• 左右指針法：取樞軸為最左邊元素（keyi所指元素），定義兩個指針pre和cur，pre用來記錄大于樞軸的元素的前驅，cur用來從左往右找小于樞軸的元素，找到了就++pre，然后pre和cur所指元素交換（cur指向右邊小于樞軸的元素，pre指向左邊大于樞軸的元素），然后++cur，否則只需要++cur，pre不動。直到cur == right，就交換pre和keyi所指向的元素，即可確定此趟排序的最終樞軸位置pre。

  • 左右指針法部分圖解：

    

  • 左右指針法代碼：

    //一趟排序  ---  左右指針法
    int PartSort3(int *a, int left, int right) {
        int pre = left;
        int cur = left + 1;
        int keyi = left;
        while (cur <= right) {
            //cur找小于樞軸的元素，找到就++pre和cur元素交換，否則cur后移繼續(xù)找
            if (a[cur] < a[keyi] && ++pre != cur) { //++pre != cur 防止自己和自己交換 這里pre已經(jīng)++了
                Swap(&a[pre], &a[cur]);
            }
            ++cur;
        }
        Swap(&a[pre], &a[keyi]);
        return pre;
    }
    

• 再來寫整體的排序代碼，即每趟選出一個樞軸元素后，就確定了它的最終位置，然后對此樞軸元素的左邊序列排序，再對對此樞軸元素的右邊序列排序。遞歸結束條件是只剩下一個元素（begin == end），或者begin > end，因為到這一步不需要排序了。

  //快速排序 -- 遞歸方法
  void QuickSort(int *arr, int begin, int end) {
      if (begin >= end)//只剩下一個元素，或者begin > end直接返回
          return;
      //先找到排序一趟后的樞軸元素的最終位置
      int pos = PartSort3(arr, begin, end);
      QuickSort(arr, begin, pos - 1);//對左邊排序
      QuickSort(arr, pos + 1, end);//對右邊排序
  }
  

  • 我們來想想，對于這個遞歸版的快速排序還能不能再優(yōu)化？答案是肯定的。我們考慮一個問題，當排序到當前序列長度就為10左右，此序列是不是基本有序了，此時遞歸深度可能已經(jīng)很深了。那基本有序了是不是可以考慮一下其他排序算法，不用遞歸的算法，可以降低遞歸深度，這里插入排序是最優(yōu)選擇。那么我們看下優(yōu)化后的代碼。其中判斷此趟序列長度可以用end - begin。

    //快速排序  -- 遞歸方法優(yōu)化
    void QuickSort(int *arr, int begin, int end) {
        if (begin >= end)//只剩下一個元素，或者begin > end直接返回
            return;
        if (end - begin <= 10) {
            //區(qū)間短短直接用插入排序，因為短區(qū)間此時基本有序了
            InsertSort(arr + begin, end - begin + 1);
        } else {
            //先找到排序一趟后的樞軸元素的最終位置
            int pos = PartSort3(arr, begin, end);
            QuickSort(arr, begin, pos - 1);//對左邊排序
            QuickSort(arr, pos + 1, end);//對右邊排序
        }
    }
    

2、快速排序（非遞歸）

2.1、快速排序（非遞歸）思想

• 快速排序（非遞歸）和快速排序（遞歸）的思想類似，但是遞歸版的使用的系統(tǒng)棧，非遞歸版則是采用人工棧來模擬遞歸的系統(tǒng)棧。即還是采用分治法，每趟排序完把這趟的序列分成兩部分。首先創(chuàng)建一個棧Stack，然后先把這整個要排序的序列的左右邊界的下標壓入棧中，這里采用先壓左邊邊界下標left（也可以先壓右邊邊界下標，出棧也得跟著變），然后壓右邊邊界下標right。接下來就是對這個整個序列入棧出棧的操作了（排序）：取這次要排序的序列區(qū)間（取棧頂元素（左邊界），再棧頂元素出棧，再取棧頂元素（右邊界），再棧頂元素出棧），然后對這個區(qū)間的序列進行劃分（確定這個序列的樞軸的最終位置pos）。然后判段這次樞軸的位置對于其左右區(qū)間是否還需要繼續(xù)劃分（pos和left、right比較，pos -1 > left，pos + 1 < right則繼續(xù)劃分），一直循環(huán)下去，直到?？?/strong>。