基本思想

1 在数据集之中，选择一个元素作为"基准"（pivot）。
2 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

举个栗子

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

JavaScript如何快速排序

    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)];
    }

输出： [2, 3, 6, 7, 8, 9, 34, 80]

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点的实践。