手撸排序：快速排序

沉迷猴姆拉无法自拔

核心思想

首先算法理解了主要思想，那么代码实现也是信手拈来

快排分以下三步：

• 找基准：挑一个基准数用来分割当前数组，我们称该数为"基准"(pivot)
• 分割：把数组里小于"基准"的数放到左边，遍历一遍操作后数组就分割好了，最麻烦的也是这步分割操作了
• 递归：对分割后的数组重复第一二步，直到最后数组长度为1或0，就代表已经排好可以返回了

算法示意图（图源维基百科）

实例分析

首先我们用lodash创建一个随机数组

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

现在将它进行排序

首先选取基准数，我们就直接取最后一位作为基准数，左起设一个index值记录替换次数，每替换一次index自增1

然后从左至右开始遍历

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 2替换下标为0，0的两个数，index自增1，

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 3替换下标为1，1的两个数，index自增1

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 4替换下标为2，2的两个数，index自增1

[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 1替换下标为3，3的两个数，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替换下标为4, 5的两个数，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 ]
// 遍历结束替换pivot与index下标的值，这样就分割出了两个数组
[2, 3, 4, 1, 5]
[8, 10, 9, 7]
// 然后再分别将这两个数组进行重复上述操作

有了上述思路就可以开始撸代码了

// 定义交换逻辑
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
}

代码可能较其他方法冗余，个人认为这是思路最清晰的写法

测试

然后加一些测试代码

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