js算法-快速排序(Quicksort)

Taste 發(fā)布于2019-08-23 14:35 / 1415人閱讀

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

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

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

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

從數(shù)組中選擇一個元素作為基準點

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

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

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

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

選擇左右邊的元素為基準數(shù)，7

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

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

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

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

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

以上就是快速排序基本的一個實現(xiàn)思想。

快速排序?qū)崿F(xiàn)方式一

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

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));
};

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

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

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

首先我們每次執(zhí)行都會使用到兩個數(shù)組空間，產(chǎn)生空間復雜度。

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

對大量數(shù)據(jù)的排序來說相對會比較慢

優(yōu)點：

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

非常適合用于面試筆試題

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

快速排序的實現(xiàn)方式二

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

初始化i = -1

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

循環(huán)結(jié)束后，最后將支點與i+1位置的元素進行交換位置

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

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

先寫最簡單的數(shù)組交換吧，這個大家應(yīng)該都懂

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

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

/**
 * 
 * @param {*} A  數(shù)組
 * @param {*} p  起始下標
 * @param {*} r  結(jié)束下標 + 1
 */
 function dvide(A, p, r){
    // 基準點
    const pivot = A[r-1];
    
    // i初始化是-1，也就是起始下標的前一個
    let i = p - 1;
    
    // 循環(huán)
    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;
 }

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

    /**
     * 
     * @param {*} A  數(shù)組
     * @param {*} p  起始下標
     * @param {*} r  結(jié)束下標 + 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  數(shù)組
 * @param {*} p  起始下標
 * @param {*} r  結(jié)束下標 + 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  數(shù)組
 * @param {*} p  起始下標
 * @param {*} r  結(jié)束下標 + 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;
}

總結(jié)

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