引子
快速排序是一个很难记的概念，倒不是说排序方法难记，就是为什么叫快速排序，到底快在哪儿，说不清楚。
回味归并排序
- 数组对半分，不停对半分
- 直到数组长度为1，即已排好，因为长度为1根本不用排
- 用merge将两个长度为1的数组合并，并排好序
- 用merge将两个长度为2的数字合并，并排好序
- ……
a1..n, n=1
sort(a1,...,an){ a1>a2?[a2,a1]:[a1:a2], n=2
merge(sort(a1..n/2),sort(an/2+1...n), n>=3
快速排序
人类思维：
- 以某个元素为基准pivot，小的往左走，大的往右走
- 将分好的左边和右边递归，直到各部分只剩下一个元素
数学思维：
an, n=1
sort(a1,...,an){
sort(a1,...,an - ap).filter(value < ap) + ap + sort(a1,...,an - ap).filter(value >= ap), n>=2
// - ap 表示从数组里删除ap
代码：
quickSort = (arr = []) => {
if (arr.length <=1) return arr
let [pivot, ...rest] = arr
return [
...quickSort(rest.filter(n => n < pivot),
pivot,
...quickSort(rest.filter(b => n > pivot)
]
}
- 从数学方法转变成代码真的很简单，但也是一直提到的数学方法是不考虑复杂度的
- 每个filter都在遍历，每次解构都在开辟新数组空间
就地排序
从归并排序的经验来看，解决数组排序时频繁开辟空间和遍历的方法就是采用就地排序
- 在原数组进行操作
- 尽量使用交换，而不是插入删除，因为插入会导致整个数组前进或后退
回忆人类思维，人类思维一般复杂度低，因为靠大脑硬想的，都不会太复杂
小的往左走，大的往右走
- 一般选择arr[0]为基准，因为数字是随机的，不需要选择数组中间
- 遍历arr，小的插到a[0]左边，大的就继续往下走
- 但这样会导致频繁的数组整体移动
双指针交换
- 遇到小的和左边pivot交换，左指针+1
- 遇到大的和右边交换，右指针-1，继续比较当前指针
- 左右指针相遇，则一次排序完成
问题： pivot一直在移动，需要单独保存当前pivot位置
pivot
- 遇到小的和pivot右边的值交换，即arr[povot + 1],在这里是arr[1]
- 左右指针相遇时，将pivot和左边的小数组最后一个交换，即swap(arr, start, left - 1)
// in-place
quickSort = (arr, start, end) => {
if (!arr || arr.length <=1 || end - start <= 1) return arr
if (!end) end = arr.length
if (!start) start = 0
// 一次排序算出pivot后的index
const sortedIndex = oneSort(arr, start, end)
// 如果返回false，则表示排序结束不需要继续递归了
if (sortedIndex === false) {
return arr
}
// 对pivot左边的小数组进行递归排序
quickSort(arr, start, sortedIndex)
// 对pivot左边的大数组进行递归排序
quickSort(arr, sortedIndex + 1, end)
return arr
}
oneSort = (arr = [], start, end) => {
// 如果end和start差距1，因为前开后闭，表示不需要排序了
if (end - start <= 1) return false
let pivot = arr[start]
let left = start + 1
let right = end - 1
while(left <= right) {
if (arr[left] <= pivot ) {
swap(arr, start + 1, left)
left += 1
} else {
swap(arr, left, right)
right -= 1
}
}
// 将小数组的末端和pivot交换
swap(arr, start, left - 1)
// 返回pivot的位置
return left - 1
}
swap = (arr, leftIndex, rightIndex) => {
[arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]]
}
随机选择pivot
- 正常来说快排的时间复杂度是O(n * log n),因为基本每次是对半分数组的
- 但是如果你每次都选择了整个数组最大或者最小的数，那么复杂度就会变成O(n*n)
- 如果我们每次都随机选一个pivot，总不能还每次最小吧
oneSort = (arr = [], start, end) => {
if (end - start <= 1) return false
// sort前把数组第0个和随机位置调换
swap(arr, start, Math.floor(Math.random() * Math.floor(end)))
let pivot = arr[start]
let left = start + 1
let right = end - 1
while(left <= right) {
if (arr[left] <= pivot ) {
swap(arr, start + 1, left)
left += 1
} else {
swap(arr, left, right)
right -= 1
}
}
swap(arr, start, left - 1)
return left - 1
}
总结
快排的数学思路十分清晰，但是优化起来却需要考虑非常多，在边际问题上也很烧脑。
打log做辅助，进而确定代码是否按自己的思考准确执行，是相当关键的
接着就是还是要多留意一下，这，就是快排。不要再忘了。
