js算法-快速排序(Quicksort)

Taste 發布于2019-08-23 14:35 / 1409人閱讀

摘要：快速排序英語，又稱劃分交換排序，簡稱快排，一種排序算法，最早由東尼霍爾提出。

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序n個項目要O(nLogn)次比較。在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實上，快速排序O(nLogn)通常明顯比其他算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成

快速排序可能大家都學過，在面試中也經常會遇到，哪怕你是做前端的也需要會寫，這里會列舉兩種不同的快排代碼進行分析

快速排序的3個基本步驟：

從數組中選擇一個元素作為基準點

排序數組，所有比基準值小的元素擺放在左邊，而大于基準值的擺放在右邊。每次分割結束以后基準值會插入到中間去。

最后利用遞歸，將擺放在左邊的數組和右邊的數組在進行一次上述的1和2操作。

為了更深入的理解，可以看下面這張圖

我們根據上面這張圖，來用文字描述一下

選擇左右邊的元素為基準數，7

將小于7的放在左邊，大于7的放在右邊，然后將基準數放到中間

然后再重復操作從左邊的數組選擇一個基準點2

3比2大則放到基準樹的右邊

右邊的數組也是一樣選擇12作為基準數，15比12大所以放到了12的右邊

最后出來的結果就是從左到右 2 ，3，7，12，15了

以上就是快速排序基本的一個實現思想。

快速排序實現方式一

這是我最近看到的一種快排代碼

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

以上代碼的實現方式是，選擇一個中間的數字為基準點，用兩個數組分別去保存比基準數小的值，和比基準數大的值，最后遞歸左邊的數組和右邊的數組，用concat去做一個數組的合并。

對于這段代碼的分析：
缺點：

獲取基準點使用了一個splice操作，在js中splice會對數組進行一次拷貝的操作，而它最壞的情況下復雜度為O(n)，而O(n)代表著針對數組規模的大小進行了一次循環操作。

首先我們每次執行都會使用到兩個數組空間，產生空間復雜度。

concat操作會對數組進行一次拷貝，而它的復雜度也會是O(n)

對大量數據的排序來說相對會比較慢

優點：

代碼簡單明了，可讀性強，易于理解

非常適合用于面試筆試題

那么我們接下來用另外一種方式去實現快速排序

快速排序的實現方式二

從上面這張圖，我們用一個指針i去做了一個分割

初始化i = -1

循環數組，找到比支點小的數就將i向右移動一個位置，同時與下標i交換位置

循環結束后，最后將支點與i+1位置的元素進行交換位置

最后我們會得到一個由i指針作為分界點，分割成從下標0-i，和 i+1到最后一個元素。

下面我們來看一下代碼的實現，整個代碼分成三部分，數組交換，拆分，qsort（主函數）三個部分

先寫最簡單的數組交換吧，這個大家應該都懂

    function swap(A, i ,j){
        const t = A[i];
        A[i] = A[j];
        A[j] = t;
    }

下面是拆分的過程，其實就是對指針進行移動，找到最后指針所指向的位置

/**
 * 
 * @param {*} A  數組
 * @param {*} p  起始下標
 * @param {*} r  結束下標 + 1
 */
 function dvide(A, p, r){
    // 基準點
    const pivot = A[r-1];
    
    // i初始化是-1，也就是起始下標的前一個
    let i = p - 1;
    
    // 循環
    for(let j = p; j < r-1; j++){
        // 如果比基準點小就i++，然后交換元素位置
        if(A[j] <= pivot){
            i++;
            swap(A, i, j);
        }
    }
    // 最后將基準點插入到i+1的位置
    swap(A, i+1, r-1);
    // 返回最終指針i的位置
    return i+1;
 }

主程序主要是通過遞歸去重復的調用進行拆分，一直拆分到只有一個數字。

    /**
     * 
     * @param {*} A  數組
     * @param {*} p  起始下標
     * @param {*} r  結束下標 + 1
     */
    function qsort(A, p, r){
        r = r || A.length;
        if(p < r - 1){
            const q = divide(A, p, r);
            qsort(A, p, q);
            qsort(A, q + 1, r);
        }
        return A;
    }

完整代碼

function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}

/**
 *
 * @param {*} A  數組
 * @param {*} p  起始下標
 * @param {*} r  結束下標 + 1
 */
function divide(A, p, r) {
  const x = A[r - 1];
  let i = p - 1;

  for (let j = p; j < r - 1; j++) {
    if (A[j] <= x) {
      i++;
      swap(A, i, j);
    }
  }

  swap(A, i + 1, r - 1);

  return i + 1;
}

/**
 * 
 * @param {*} A  數組
 * @param {*} p  起始下標
 * @param {*} r  結束下標 + 1
 */
function qsort(A, p = 0, r) {
  r = r || A.length;

  if (p < r - 1) {
    const q = divide(A, p, r);
    qsort(A, p, q);
    qsort(A, q + 1, r);
  }

  return A;
}

總結

第二段的排序算法我們減少了兩個O(n)的操作，得到了一定的性能上的提升，而第一種方法數據規模足夠大的情況下會相對來說比較慢一些，快速排序在面試中也常常出現，為了筆試更好寫一些可能會有更多的前端會選擇第一種方式，但也會有一些為難人的面試官提出一些算法中的問題。而在實際的項目中，我覺得第一種方式可以少用。