前言

原文：[ javascript: 快速排序（Quick Sort） #146 ]

基本思想

1 在數據集之中，選擇一個元素作為"基準"（pivot）。
2 所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。
3 對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。

舉個栗子

let array = [2, 9, 6, 3, 80, 34, 7, 8];

function quickSort(list) {
  if(list.length <= 1) { return list; }
  let left = [], right = [];
  let pivotIndex = Math.floor(list.length / 2);
  let pivot = list.splice(pivotIndex, 1)[0];
  
  for(let index = 0, len = list.length; index < len; index++) {
    let val = list[index];
    
    if(val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort函數解構

  let left = [], right = [];
  let pivotIndex = Math.floor(list.length / 2);
  let pivot = list.splice(pivotIndex, 1)[0];
  
  for(let index = 0, len = list.length; index < len; index++) {
    let val = list[index];
    
    if(val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  }

這部分邏輯正是對基本思想中的1、2點的實踐。

• 1 找出基準數

  let pivotIndex = Math.floor(list.length / 2);
  let pivot = list.splice(pivotIndex, 1)[0];

• 2 以“基準”二分數組

  for(let index = 0, len = list.length; index < len; index++) {
    let val = list[index];
    
    if(val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  }

• 3 重復1、2點

在栗子中的數組執(zhí)行一次1、2點實現(xiàn)后，你會發(fā)現(xiàn)此時執(zhí)行后出現(xiàn)三個結果
1）letf = [2];
2）pivot = 3;
3）right = [9, 6, 80, 34, 7, 8];

然后依次組合

[...left, pivot, ...right]
// [2, 3, 9, 6, 80, 34, 7, 8]

你會發(fā)現(xiàn)left只有一個元素，那就沒有必要繼續(xù)對left排序，所以沒有必要再排序

if(list.length <= 1) { return list; }

然后再看right，并不是有序數組。那要怎么辦？繼續(xù)對right排序，調用quickSort

quickSort(right)
// [...quickSort(left), pivot, ...quickSort(right)];

而

return [...quickSort(left), pivot, ...quickSort(right)];

正是對第3點的實踐。