继上一篇《（3）Go实现单路快排和随机快排》后续：
https://www.jianshu.com/p/e74ff993dd47
双路快排的算法如下：
如上图所示，分左右2个索引 //
i，j均指向当前要判定的元素e
左边的情况：
1）若arr[i]<v，直接i++
2）若arr[i]>=v，去判定右边的情况，若arr[j]>v，直接j++
3）直到arr[i]>=v且arr[j]<=v时，交换arr[i],arr[j]的值，之后i++，j--，直到i>j结束判定
这样即使arr[i]=arr[j]，也会进行一次交换，因此相同的值会较平均的分配在左右两边，
减轻分区时的不平衡性，最后左区间是<=v，右区间是>=v
双路排序的实现 //
func QuickSort4(arr []int, l, r int) {
if l >= r {
return
}
if r-l <= 5 {
insertionSort2(arr, l, r)
}
p := Partition3(arr, l, r)
QuickSort4(arr, l, p-1)
QuickSort4(arr, p+1, r)
}
func Partition3(arr []int, l, r int) int {
v := arr[l]
// arr[l+1...j] <= v ; arr[j+1...i] >= v
leftI := l + 1
rightI := r
for {
switch {
case leftI > rightI:
// 能通过这步,说明索引全合法,不合法则说明遍历结束
arr[l], arr[rightI] = arr[rightI], v
return rightI
// 判定左边
case arr[leftI] < v:
leftI++
// 判定右边
case arr[rightI] > v:
rightI--
default:
// 以上3点都不成立,说明arr[leftI]>=v,arr[rightI]<=v,两者需要交换
arr[leftI], arr[rightI] = arr[rightI], arr[leftI]
leftI++
rightI--
}
}
}
3路快排的思路是将区间分为3部分，左边小于v，中间等于v，右边大于v，之后中间不再判定，
再分别对左边，右边进行分区，直至排序结束，如下图示：
分3种情况，e为待判定元素：
1）e==v，i++
2）e<v，交换arr[lt+1]，arr[i]位置，之后lt++，i++
3）e>v，交换arr[i]，arr[gt+1]位置，之后gt--
4）最后交换arr[l]，arr[lt]位置
3路快排的实现 //
// 将arr[l...r]分为 < v ; == v ; > v 三部分
// 之后递归对 < v , > v 两部分继续进行三路快速排序
func QuickSortThreeWays(arr []int, l, r int) {
if l < r {
lt, gt := sortThreeWays(arr, l, r)
QuickSortThreeWays(arr, l, lt-1)
QuickSortThreeWays(arr, gt, r)
}
}
func sortThreeWays(arr []int, l, r int) (lt, gt int) {
v := arr[l]
lt = l // arr[l+1...lt] < v
gt = r + 1 // arr[gt...r] > v
i := l + 1 // arr[lt+1...i) == v 半开半闭
for {
switch {
case i >= gt:
// 这步未执行前,lt都是指向最后一个小于v的值,
// 执行交换后,lt指向从左到右第一个等于v的值
arr[l], arr[lt] = arr[lt], v
return lt, gt
case arr[i] == v:
i++
case arr[i] < v:
lt++
arr[i], arr[lt] = arr[lt], arr[i]
i++
default:
gt--
arr[i], arr[gt] = arr[gt], arr[i]
}
}
}
测试
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("排序正确")
}
}
const count = 100000
nums2 := [count]int{}
for i := 0; i < count; i++ {
nums[i] = rand.Intn(5)
}
for i := 0; i < 6; i++ {
nums3 := nums2
nums := nums3[:]
switch i {
case 0:
t := time.Now()
nums = quick_sort.MergerSort(nums)
fmt.Println("递归结合插入排序时间:", t.Sub(time.Now()))
isTrue(nums)
case 1:
t := time.Now()
quick_sort.QuickSort1(nums, 0, len(nums)-1)
fmt.Println("基本单排--排序时间:", t.Sub(time.Now()))
isTrue(nums)
case 2:
t := time.Now()
quick_sort.QuickSort2(nums, 0, len(nums)-1)
fmt.Println("单排结合插入--排序时间:", t.Sub(time.Now()))
isTrue(nums)
case 3:
t := time.Now()
quick_sort.QuickSort3(nums, 0, len(nums)-1)
fmt.Println("随排结合插入--排序时间:", t.Sub(time.Now()))
isTrue(nums)
case 4:
t := time.Now()
quick_sort.QuickSort4(nums, 0, len(nums)-1)
fmt.Println("双排结合插入--排序时间:", t.Sub(time.Now()))
isTrue(nums)
case 5:
t := time.Now()
quick_sort.QuickSortThreeWays(nums, 0, len(nums)-1)
fmt.Println("3排结合插入--排序时间:", t.Sub(time.Now()))
isTrue(nums)
}
fmt.Println("----")
测试数组中重复元素多的情况：
递归结合插入--排序时间: -102.47012ms
排序正确
----
基本快速--排序时间: -2.257792194s
排序正确
----
快速结合插入--排序时间: -2.171909195s
排序正确
----
快速随机排序--排序时间: -2.739016208s
排序正确
----
双向快速排序--排序时间: -4.969555ms
排序正确
----
3路快速排序--排序时间: -1.144312ms
排序正确
结论：//
对于完全随机的数组，单排，双排，3排，速度都优于递归排序；
对于数组中存在大量重复元素的情况下，3排速度最快，双排次之；
对于偏顺序的数据，用插入排序有时反而能更快，或者用递归排序，随机3排也行
不能完全按时间复杂度，要结合具体的数据类型考量
