2020-01-24：手写代码：快速排序。
原创2020-01-24：手写代码：快速排序。
原创
福大大架构师每日一题
修改于 2021-01-25 10:45:51
修改于 2021-01-25 10:45:51
福哥答案2020-01-24：
荷兰国旗问题三分+小于区递归+大于区递归。，相等区不用管。
代码用go语言编写。利用slice特性，可以节省两个参数。代码如下：
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
sucCount := 0
failedCount := 0
for i := 0; i < 2000; i++ {
arr1 := GenRandArr()
arr2 := make([]int, len(arr1))
fmt.Println("原数组：", arr1)
copy(arr2, arr1)
BubbleSort(arr1)
QuickSort(arr2)
fmt.Println("冒泡排序", arr1)
fmt.Println("快速排序", arr2)
fmt.Println("--------")
if IsEqual(arr1, arr2) {
sucCount++
} else {
failedCount++
}
}
fmt.Println("成功：", sucCount)
fmt.Println("失败：", failedCount)
}
//荷兰国旗问题三分
func partition(arr []int, val int) (int, int) {
lessEqual := -1
moreEqual := len(arr)
index := 0
for index < moreEqual {
if arr[index] < val { //左区右扩
lessEqual++
arr[index], arr[lessEqual] = arr[lessEqual], arr[index]
index++
} else if arr[index] > val { //右区左扩，注意index不会++
moreEqual--
arr[index], arr[moreEqual] = arr[moreEqual], arr[index]
} else { //相等区
index++
}
}
return lessEqual, moreEqual
}
//三分随机快排递归
func QuickSort(arr []int) {
arrLen := len(arr)
if arrLen < 2 {
return
}
//荷兰国旗问题三分，以数组中的随机1个元素划分
left, right := partition(arr, arr[rand.Intn(arrLen)])
//左边快排
QuickSort(arr[0 : left+1])
//右边快排
QuickSort(arr[right:])
}
//for test
func GenRandArr() []int {
ret := make([]int, rand.Intn(20)+10)
retLen := len(ret)
for i := 0; i < retLen; i++ {
ret[i] = rand.Intn(100)
}
return ret
}
//for test
func BubbleSort(arr []int) {
arrLen := len(arr)
if arrLen < 2 {
return
}
for i := 0; i < arrLen-1; i++ {
for j := 0; j < arrLen-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
//for test
func IsEqual(arr1 []int, arr2 []int) bool {
arr1Len := len(arr1)
for i := 0; i < arr1Len; i++ {
if arr1[i] != arr2[i] {
return false
}
}
return true
}执行结果如下：
在这里插入图片描述
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读