快速排序

https://github.com/mohuishou/go-sort

说明

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

步骤

  • 从数列中挑出一个元素,称为 “基准”(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

注意: 基准点采用三元素原则法,三元素选择之后一头一尾就已经有序了

示例

示例图片

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package quik

//Sort 快速排序
func Sort(arr []int) {
Quik(arr, 0, len(arr)-1)
}

//Quik 快速排序递归实现
func Quik(arr []int, left int, right int) {
if right-left < 2 {
return
}
p := middle3(arr, left, right)

i := left + 1
j := right - 2
for {
for arr[i] < p {
i++
}
for arr[j] > p {
j--
}
if i < j {
arr[i], arr[j] = arr[j], arr[i]
} else {
break
}
}
arr[i], arr[right-1] = arr[right-1], arr[i]
Quik(arr, left, i-1)
Quik(arr, i+1, right)
}

func middle3(arr []int, left int, right int) int {
center := (right + left) / 2
if arr[left] > arr[center] {
arr[left], arr[center] = arr[center], arr[left]
}
if arr[left] > arr[right] {
arr[left], arr[right] = arr[right], arr[left]
}
if arr[center] > arr[right] {
arr[center], arr[right] = arr[right], arr[center]
}
arr[center], arr[right-1] = arr[right-1], arr[center]
return arr[right-1]
}