快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(n log n)次比较。在最坏状况下则需要 Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。
步骤:
1.从数列中挑出一个元素,称为 “基准”(pivot),
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
注意: 基准点采用三元素原则法,三元素选择之后一头一尾就已经有序了
实现
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]
}