快速排序和递归排序一样，思想都是分治法，即将问题划分为若干相互独立的个小问题，这些问题和该问题具有相同的特征，将这些小问题解决后，该问题也解决了。
在最好的情况下，每次都平均分成2半，n个数字分log2N次能分完，每次遍历n个数值，时间复杂度为log2Nn=logNn。在最差的情况下，每次分都分成1和n-1半，这样要n次才能分完，时间复杂度会变成 n*n
不同点在于递归排序是直接将数组平均分组，而快速排序是以某个值v为基准，分组后，左边的值小于v，右边的值大于v，等于的情况放左边右边都可以，如下图示：
以数组首个值4为基准示例，分组后左边的值都小于4，右边的值都大于4，之后分别继续对
左边小于4的部分和右边大于4的部分进行分组，依此完成排序
单路快速排序的实现
// 单路快速排序,前闭后闭
func QuickSort1(arr []int, l, r int) {
if l >= r {
return
}
p := Partition1(arr, l, r)
QuickSort1(arr, l, p-1)
QuickSort1(arr, p+1, r)
}
func Partition1(arr []int, l, r int) int {
v := arr[l]
j := l
for i := l + 1; i <= r; i++ {
if arr[i] < v {
j++
arr[j], arr[i] = arr[i], arr[j]
}
}
// 如果没有发生交换,j 最终是和自己发生交换,数组不变
arr[j], arr[l] = v, arr[j]
return j
}
测试
// 测试排序结果是否正确
func isTrue(nums []int) {
b := true
for i := 1; i < count; i++ {
if nums[i-1] > nums[i] {
fmt.Println("排序错误", nums[i-1], nums[i])
b = false
break
}
}
if b {
fmt.Println("排序正确")
}
}
func main() {
const count = 10000
t := time.Now()
quick_sort.QuickSort1(nums, 0, len(nums)-1)
fmt.Println("基本快速排序时间:", t.Sub(time.Now()))
isTrue(nums)
}
测试结果
1）数组完全随机
nums := []int{}
for i := 0; i < count; i++ {
nums[i] = rand.Intn(count )
}
基本快速排序时间: -1.042074ms
排序正确
2）数组有序
nums := []int{}
for i := 0; i < count; i++ {
nums[i] = count-i
}
基本快速排序时间: -161.286566ms
排序正确
分析：两者时间差距100多倍，原因是每次都取数组首个值为基准，这样分区后左右数组及不平衡，
在最坏的情况下，快排的时间复杂度会退化成O(n^2)，如下图示：
解决方法是不要每次都取首个字母为基准，而是随机取一个数为基准，改动后的快排如下：
// 单路随机快排
func QuickSort2(arr []int, l, r int) {
if l >= r {
return
}
// 随机数为基准
p := Partition2(arr, l, r)
QuickSort3(arr, l, p-1)
QuickSort3(arr, p+1, r)
}
func Partition2(arr []int, l, r int) int {
// 随机取1个值为基准
randIndex := randInt(l, r)
arr[l], arr[randIndex] = arr[randIndex], arr[l]
v := arr[l]
j := l
for i := l + 1; i <= r; i++ {
if arr[i] < v {
j++
arr[j], arr[i] = arr[i], arr[j]
}
}
arr[j], arr[l] = v, arr[j]
return j
}
func randInt(l, r int) int {
rand.Seed(time.Now().UnixNano())
return l + rand.Intn(r-l)
}
测试单路快排和单路随机快排：
const count = 100000
nums := []int{}
for i := 0; i < count; i++ {
nums[i] = count-i
}
t1 := time.Now()
quick_sort.QuickSort1(nums, 0, len(nums)-1)
fmt.Println("基本快速排序时间:", t1.Sub(time.Now()))
isTrue(nums)
t2 := time.Now()
quick_sort.QuickSort2(nums, 0, len(nums)-1)
fmt.Println("基本快速排序时间:", t2.Sub(time.Now()))
isTrue(nums)
测试结果 //
基本快速排序时间: -14.446320539s
排序正确
----
快速随机排序排序时间: -782.599245ms
排序正确
结论：每次随机取值为基准，能避免快速排序往最坏的情况发展，加快排序时间。
继续测试，当数据存在大量重复元素时，结果又会怎样？
const count = 100000
for i := 0; i < count; i++ {
nums2[i] = rand.Intn(5)
}
测试结果
基本快速排序时间: -2.554524223s
排序正确
----
快速随机排序排序时间: -3.0671954s
排序正确
分析，当数组中存在大量重复元素，随机快排的速度反而不如基本快排，这是因为重复元素
会偏向左边或右边，会导致分区不平均，拖慢排序时间
解决方法由两个，双路快排或3路快排：
后续《（4）Go实现双路快排，3路快排及测试》：
https://www.jianshu.com/p/37d563d5eda4
