快速排序基本原理以及JS实现

前言

高手选择排序的方式是根据具体的数据而选择不同的排序，我们这些小菜鸟该怎么办？当然是快速排序一把梭（程序员不要提冒泡了），快排基本上能满足你遇到的90%的排序需求，对于我们前端而言可能是99%。

算法原理

快速排序的基本思想是“分治”，“分治”的基本思想是把一个规模为N的问题分解成K个规模较小的子问题，这些子问题的相互独立并且与原问题性质相同，所以可以不断的递归求解。

快速排序的方法如下：

• 在给出的一组数据中选出一个基准值。
• 将这组数据中所有比基准值大的数放在右边，所有比基准值小的数放在左边，分界线就是该基准值。
• 对基准值左右两边的两组数使用同样的方式排序，不断递归，直到所有数据排序完成。

具体实现

举例：
[5, 2, 6, 9, 7, 3, 12]

1. 选出基准数，基准数的选择一般常用的有两种方式。第一种是选择该组数据的第一个数，第二种是生成一个数据总数量以内的随机数，作为基准数的数组索引，以此来选出基准数。因为从理论上我们不知道要排序的具体数据，因此使用第一种方式选择的基准数本身就是随机的，一般情况下我们使用第一种方式选出基准数，比如此例中我们选择5来作为基准数。
2. 要实现基准数左边数据都比其小，右边数据都比起大，这一步依然有两种方式。第一种是从数组左右两边分别开始搜索，从右边开始向左查找，找到第一个比基准数小的数3，然后再从左向右开始查找，找到第一个比基准数大的数6，然后交换它们的位置，最后的数据为
   [5, 2, 3, 9, 7, 6, 12]
   依次执行上面的步骤，设从左边查找的索引为left,从右边查找的索引为right,当最后left = right时，将给位置的数和基准数交换位置，最后结果为
   [3, 2, 5, 9, 7, 6, 12]
   第二种方法也被称做“填坑”法，从有向做开始查找第一个小于基准数的数3，然后将其填到left指向的位置[3, 2, 6, 9, 7, 3, 12],然后开始从左向右查找第一个大于基准数的数6，将其填到right指向的位置[3, 2, 6, 9, 7, 6, 12],然后重复以上过程，最后将left = right时指向的位置填入基准数5 ->[3, 2, 5, 9, 7, 6, 12]
3. 然后对基准数左右部分的两个数组[3, 2]和[9, 7, 6, 12]依次采用这种方法递归排序,最终得到排序完成的数组[2, 3, 5, 6, 7, 9, 12]

JavaScript代码实现：

/*第二步使用的是填坑法*/

/*
* data - 排序数组
* low - 数组最左端索引
* height - 数组最右端索引
*/

function quickSort(data, low, height) {
  let sortData = data
  let isLeft = true
  let left = low,
    right = height,
    temp = sortData[left]
  if (low >= height) {
    return sortData
  }
  while (left !== right) {
    if (isLeft) {
      if (sortData[right] < temp) {
        sortData[left] = sortData[right]
        isLeft = !isLeft
      } else {
        right--
      }
    } else {
      if (sortData[left] > temp) {
        sortData[right] = sortData[left]
        isLeft = !isLeft
      } else {
        left++
      }
    }
  }
  sortData[left] = temp
  quickSort(sortData, low, left - 1)
  quickSort(sortData, left + 1, height)
  return sortData
}