javascript: 快速排序（Quick Sort）

前言

原文：[ 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点

在栗子中的数组执行一次1、2点实现后，你会发现此时执行后出现三个结果
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]

你会发现left只有一个元素，那就没有必要继续对left排序，所以没有必要再排序

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

然后再看right，并不是有序数组。那要怎么办？继续对right排序，调用quickSort

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

而

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

正是对第3点的实践。