快速排序

[18888628835]

快速排序最早由图灵奖得主东尼·霍尔提出，是一种分而治之的排序思想。

快速排序的思想分为三步：

• 在数组中，选择一个基准点 pivot
• 遍历数组，把小于基准点的放左边，大于基准点的放后边
• 对基准点左边和右边的元素不断重复第一步和第二步，直到只剩一个元素

假设目前的元素是这样的
[1, 2, 6, 7, 3, 8, 5, 9, 4, 10]
我在中间位置取一个基准点8，然后把小于8的都放到左边，大于8的都放到右边
[1,2,6,7,3,5,4]8[9,10]
然后再把左边的数组重新按照上面的步骤走一遍
[1,2,6,3,5,4,]7[]
右边的也这样走一遍
[9]10[]
继续
[1,2]3[6,5,4]
...
最后全部合并起来。
实现代码

function quickSort(arr) {
  //如果数组的长度在1个以内，就不需要排序了直接返回,同时也是递归的停止条件
  if (arr.length < 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2); // 选择基准
  let pivot = arr.splice(pivotIndex, 1)[0]; //把基准拿出来
  let left: unknown[] = []; //放比基准小的元素
  let right: unknown[] = []; //放比基准大的元素
  //循环遍历，把元素放到对应的子集数组中
  for (let 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));
}

源码：快速排序