前言
高手选择排序的方式是根据具体的数据而选择不同的排序，我们这些小菜鸟该怎么办？当然是快速排序一把梭（程序员不要提冒泡了），快排基本上能满足你遇到的90%的排序需求，对于我们前端而言可能是99%。
算法原理
快速排序的基本思想是“分治”，“分治”的基本思想是把一个规模为N的问题分解成K个规模较小的子问题，这些子问题的相互独立并且与原问题性质相同，所以可以不断的递归求解。
快速排序的方法如下：
- 在给出的一组数据中选出一个基准值。
- 将这组数据中所有比基准值大的数放在右边，所有比基准值小的数放在左边，分界线就是该基准值。
- 对基准值左右两边的两组数使用同样的方式排序，不断递归，直到所有数据排序完成。
具体实现
举例：
[5, 2, 6, 9, 7, 3, 12]
- 选出基准数，基准数的选择一般常用的有两种方式。第一种是选择该组数据的第一个数，第二种是生成一个数据总数量以内的随机数，作为基准数的数组索引，以此来选出基准数。因为从理论上我们不知道要排序的具体数据，因此使用第一种方式选择的基准数本身就是随机的，一般情况下我们使用第一种方式选出基准数，比如此例中我们选择5来作为基准数。
- 要实现基准数左边数据都比其小，右边数据都比起大，这一步依然有两种方式。第一种是从数组左右两边分别开始搜索，从右边开始向左查找，找到第一个比基准数小的数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, 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
}
