快速排序是大多数语言内置 sort 函数的默认实现方式，简单可分为两路排序和三路排序，我在相关资料中，发现两路排序也有多种实现方式。
有些语言 sort 函数会包含 快速 希尔 插入 多种形式。
排序描述
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
排序实现
两路快排
两路快排的逻辑
严蔚敏版
这个名词来自于 b 站的评论，这个快排思路很容易理解，非常适合入门
func quickSortV1(arr []int, low, hight int) {
// 当 low = hight 时跳出
if low >= hight {
return
}
left, right := low, hight
pivot := arr[left] // 为了简单起见，直接取左边的第一个数
for left < right {
// 先从右边开始迭代
// 右边的数如果比pivot大，那么就应该将他放在右边，继续向左滑动，遇到一个比他小的为止
for left < right && arr[right] >= pivot {
right--
}
// 小数移动到左边
if left < right {
arr[left] = arr[right]
}
// 左边的数如果比pivot小，那么就应该将他放在左边，继续向右滑动，遇到一个比他大的为止
for left < right && arr[left] < pivot {
left++
}
// 大数移动到又边
if left < right {
arr[right] = arr[left]
}
// left == right ,pivot 即是最终位置
if left <= right {
arr[left] = pivot
}
}
//因为 pivot 的最终位置已锁定
// 继续排序左边部分
quickSortV1(arr, low, right-1)
// 继续排序右边部分
quickSortV1(arr, right+1, hight)
}
优化版2
func quickSortV2(arr []int, low, hight int) {
if low >= hight {
return
}
left, right := low, hight
pivot := arr[(low+hight)/2] // 这里的经验值取的是中间数，经过 Benchmark 测试，确实比较优秀
for left <= right {
// 从左边开始迭代
// 左边的数如果比 pivot 小，那么就应该将他放在左边，继续向右滑动，遇到一个比他大的为止
for arr[left] < pivot {
left++
}
// 右边的数如果比 pivot 大，那么就应该将他放在右边，继续向左滑动，遇到一个比他小的为止
for arr[right] > pivot {
right--
}
// 这里进行一次交换，将上面碰到的大数和小数交换一次
//left 继续右走，right 继续左走 注意这里还不一定相遇，去继续执行上面的逻辑
if left <= right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
// 【 xxx[xxxxx]xxxxxx】
// 【 xxxxxx][xxxxxxxx】
// [] => left,right
// 【】 => low,hight
quickSortV2(arr, low, right)
quickSortV2(arr, left, hight)
}
大体上和第一个版本差不多，但是函数更加简洁了，
优化版3
func quickSortV3(arr []int, left, right int) {
if left >= right {
return
}
cur, lo := left+1, left
for cur <= right {
if arr[cur] <= arr[left] {
arr[lo+1], arr[cur] = arr[cur], arr[lo+1]
lo++
}
cur++
}
arr[left], arr[lo] = arr[lo], arr[left]
quickSortV3(arr, left, lo-1)
quickSortV3(arr, lo+1, right)
}
这个版本是所有快速排序中，看起来比较难以理解，只有一个指针，从左到右滑动，设计非常巧妙。
pivot 经验值对结果的影响
func BenchmarkQuickSortV2(b *testing.B) {
arr := rand.Perm(math.MaxInt16)
b.ResetTimer()
for i := 0; i < b.N; i++ {
quickSortV2(arr, 0, len(arr)-1)
}
// pivot center： BenchmarkQuickSortV2-8 2529 427417 ns/op 0 B/op 0 allocs/op
// pivot left： BenchmarkQuickSortV2-8 100 211982204 ns/op 0 B/op 0 allocs/op
// pivot right： BenchmarkQuickSortV2-8 100 258063634 ns/op 0 B/op 0 allocs/op
// pivot random： BenchmarkQuickSortV2-8 913 1303080 ns/op 0 B/op 0 allocs/op
}
这边测试了四种情况，中间值最优。
三路快排
func quickSort3(arr []int, left, right int) {
if left >= right {
return
}
pivot := arr[left]
lo, gt, cur := left, right+1, left+1
for cur < gt {
if arr[cur] < pivot {
arr[cur], arr[lo+1] = arr[lo+1], arr[cur]
lo++
cur++
} else if arr[cur] > pivot {
arr[cur], arr[gt-1] = arr[gt-1], arr[cur]
gt--
} else {
cur++
}
}
arr[left], arr[lo] = arr[lo], arr[left]
quickSort3(arr, left, lo-1)
quickSort3(arr, gt, right)
}
用了3个指针，表示小于，等于，大于三个部分，从而减少相等的数在其中来回交换。
总结
由此可见快速排序是一种不稳定的排序，对于数据本身是有要求，对于 pivot 如何取也是有要求，属于经验取值了，如果对于源数据是逆序的情形，快排会退化成冒泡。
参考文档
2021年03月18日22:24 更新
快排的迭代形式实现
type Range struct {
low int
height int
}
func sort(arr []int) {
list := []Range{
{
low: 0,
height: len(arr) - 1,
},
}
for len(list) > 0 {
top := list[0]
list = list[1:]
left, right := top.low, top.height
piovt := arr[(right-left)/2+left]
for left <= right {
for arr[left] < piovt {
left++
}
for arr[right] > piovt {
right--
}
if left <= right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
if top.low < right {
list = append(list, Range{top.low, right})
}
if left < top.height {
list = append(list, Range{left, top.height})
}
}
}
网友评论