排序简介(采用了分治+递归)
- 从数列中挑出一个元素,称为 “基准”(pivot)
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
复杂度
- 平均时间复杂度:T(n) = O(nlogN)
- 最佳情况:T(n) = O(nlogN)
- 最坏情况:T(n) = O(n2)
- 空间复杂度:O(logN)
- 稳定性:不稳定
排序方式:In-place
golang实现
package main
import "fmt"
// 快速排序
func partion(arr []int, start, end int) int {
pivot, i, j := arr[start], start, end
// 将第一个元素作为pivot
for i < j {
for i < j && pivot < arr[j] { // 从右边开始找出小于pivot
j--
}
if i < j {
arr[i] = arr[j]
i++
}
for i < j && arr[i] < pivot { // 找出大于pivot
i++
}
if i < j {
arr[j] = arr[i]
j--
}
}
arr[i] = pivot //这时i是pivot最终位置
return i
}
func QuickSort(arr []int, start, end int) {
if start < end {
d := partion(arr, start, end)
QuickSort(arr, start, d-1)
QuickSort(arr, d+1, end)
}
}
func main() {
arr := []int{33,11,55,7,44,1}
QuickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
有疑问加站长微信联系(非本文作者)