沉迷猴姆拉無法自拔

核心思想

首先算法理解了主要思想，那么代碼實(shí)現(xiàn)也是信手拈來

快排分以下三步：

• 找基準(zhǔn)：挑一個基準(zhǔn)數(shù)用來分割當(dāng)前數(shù)組，我們稱該數(shù)為"基準(zhǔn)"(pivot)
• 分割：把數(shù)組里小于"基準(zhǔn)"的數(shù)放到左邊，遍歷一遍操作后數(shù)組就分割好了，最麻煩的也是這步分割操作了
• 遞歸：對分割后的數(shù)組重復(fù)第一二步，直到最后數(shù)組長度為1或0，就代表已經(jīng)排好可以返回了

算法示意圖（圖源維基百科）

實(shí)例分析

首先我們用lodash創(chuàng)建一個隨機(jī)數(shù)組

_.shuffle([1,2,3,4,5,6,7,8,9,10])
//  [2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]

現(xiàn)在將它進(jìn)行排序

首先選取基準(zhǔn)數(shù)，我們就直接取最后一位作為基準(zhǔn)數(shù)，左起設(shè)一個index值記錄替換次數(shù)，每替換一次index自增1

然后從左至右開始遍歷

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 2替換下標(biāo)為0，0的兩個數(shù)，index自增1，

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 3替換下標(biāo)為1，1的兩個數(shù)，index自增1

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 4替換下標(biāo)為2，2的兩個數(shù)，index自增1

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 1替換下標(biāo)為3，3的兩個數(shù)，index自增1

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 < 7不替換，index為4不變

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 5替換下標(biāo)為4, 5的兩個數(shù)，index自增1

[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 8不替換，index為5不變

[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 10不替換，index為5不變

[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 9不替換，index為5不變

[2, 3, 4, 1, 5, 6, 8, 10, 9, 7 ]
// 遍歷結(jié)束替換pivot與index下標(biāo)的值，這樣就分割出了兩個數(shù)組
[2, 3, 4, 1, 5]
[8, 10, 9, 7]
// 然后再分別將這兩個數(shù)組進(jìn)行重復(fù)上述操作

有了上述思路就可以開始擼代碼了

// 定義交換邏輯
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// 定義分割邏輯
function partition(arr, left, right) {
  const pivot = arr[right];
  let index = left;
  for (let i = left; i < right; i++) {
    if (pivot > arr[i]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, right, index);
  return index;
}

function sort(arr, left, right) {
  if (left > right) return;
  const index = partition(arr, left, right);
  sort(arr, left, index - 1);
  sort(arr, index + 1, right);
}

function quick_sort(arr) {
  sort(arr, 0, arr.length - 1);
  return arr
}

代碼可能較其他方法冗余，個人認(rèn)為這是思路最清晰的寫法

測試

然后加一些測試代碼

const _ = require('lodash');
const arr = _.shuffle([1,2,3,4,5,6,7,8,9,10]);
console.log(arr);
console.log(quick_sort(arr));
// [ 8, 3, 9, 4, 7, 1, 6, 2, 5, 10 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

// [ 2, 8, 4, 3, 9, 5, 1, 10, 6, 7 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

// [ 10, 7, 8, 4, 6, 1, 2, 9, 3, 5 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

測試ok