排序：快速排序

原理

以数组升序排列来说，快速排序先在一个数组中确定一个中轴元素。
比中轴元素小的元素放在左边，比中轴元素小的元素放在右边，以此来将数组切分成子数组。
接着在子数组中再确定各自的中轴元素，继续切分。然后在切出的数组中继续切分... 直到不能再切分。
这样一来，当每个小的子数组成为了有序的数组，自然而然，整个数组也就是有序的。

中轴元素是怎么确定的？一般取的是数组的第一个元素。

例子

假如给定以下数组，需要将它升序排列。

[3, 2, 7, 1, 4, 8]

首先将第一个数字 3 指定为中轴元素。

第一次切分

当 low 位置的元素小于 povit，low 向右遍历，
当 high 位置的元素大于 povit, high 向左遍历。
当 high 位置的元素小于 pivot，且 low 位置的元素大于 pivot，则交换这两个元素的位置。

当 low 和 high 相遇时，结束它们的遍历。

交换 high 位置和 povit 位置的元素。

整理：

这样，第一次切分完成。左边部分的是比 pivot 小的，右边部分是比 pivot 大的。

第二次切分

切分比原来 pivot 小的那一部分，即：

[1, 2]

远远看去已经排好序了。
好了，第二次切分结束。

第三次切分

切分比原来 pivot 大的那一部分，即：

[7, 4, 8]

参考第一次切分：

第三次切分结束。

现在整个数组是这样的：

[1, 2, 3, 4, 7, 8]

排序结束。

代码

/**
 * 指定数组，交换数组中两个元素的位置
 * @param {Array} list 数组
 * @param {Number} i 元素 1 的索引
 * @param {Number} j 元素 2 的索引
 */
const swap = (list, i, j) => {
  let temp = list[i]
  list[i] = list[j]
  list[j] = temp
}

// 快速排序
const  quickSort = (list) => {
    const qucikSort = (list, lo, hi) => {
      if (lo < hi) {
        let povitIndex = partition(list, lo, hi)
        qucikSort(list, povitIndex + 1, hi)
        qucikSort(list, lo, povitIndex - 1)
      }
    }

    // 切分
    const partition = (list, lo, hi) => {
      let i = lo
      let j = hi + 1
      let povit = list[lo]
      while (true) {
        
        while (list[--j] > povit) {
          if (j === lo) {
            break
          }
        }
        
        while (list[++i] < povit) {
          if (i === hi) {
            break
          }
        }

        if (i >= j) {
          break
        }

        swap(list, i, j)
      }

      swap(list, lo, j)

      return j
    }

    qucikSort(list, 0, list.length - 1)

    return list
}

代码中的 lo 即为 low, hi 即 high; i 和 j 分别对应遍历数组时的 low 和 high。