写点什么

用 go 语言实现快排

用户头像
Sean
关注
发布于: 2020 年 09 月 29 日
用go语言实现快排

面试的时候,常会让你手写快排代码。思路清楚了,在10分钟是可以写出来的。关于快排,需要注意一下几点:

  • 快排是本地排序

  • 快排有递归

  • 快排需要分割数据,分割函数(建议)以最后一个数据为参考,将数据分割为大小两列,最后返回参考数据所在的位置



好的函数名可以更好地体现思路。这是最近重构的版本,重新修改了函数名,理顺了一下思路,在这里做个记录。



package algorithm
import (
"math/rand"
"testing"
"time"
)
func quickSort(data []int) {
sortWithinScope(data, 0, len(data)-1)
}
// 在指定范围内排序
func sortWithinScope(data []int, start int, end int) {
if start < end {
pivot := partition(data, start, end)
sortWithinScope(data, start, pivot-1)
sortWithinScope(data, pivot+1, end)
}
}
// 将指定范围内的数据分成大小两列,返回中间参考值的位置
func partition(data []int, start int, end int) int {
ref := data[end]
nextLowerIndex := start
for i := start; i < end; i++ {
if data[i] < ref {
data[nextLowerIndex], data[i] = data[i], data[nextLowerIndex]
nextLowerIndex++
}
}
data[nextLowerIndex], data[end] = data[end], data[nextLowerIndex]
return nextLowerIndex
}
// 比较两列数据是否相同
func equal(a, b []int) bool {
if len(a) != len(b) {
return false
}
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}
func TestEmpty(t *testing.T) {
count := 10
toSort := make([]int, 0)
expect := make([]int, 0)
for i := 0; i < count; i++ {
toSort = append(toSort, i)
expect = append(expect, i)
}
// 打乱有序数组
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(toSort), func(i, j int) { toSort[i], toSort[j] = toSort[j], toSort[i] })
quickSort(toSort)
if !equal(expect, toSort) {
t.Error("soft failed")
}
}



发布于: 2020 年 09 月 29 日阅读数: 462
用户头像

Sean

关注

将学到知识用于建设美好生活。 2019.04.09 加入

前Android开发,业余小程序开发,专业后端开发。在码中参悟抽象、架构、计算的本质而乐此不疲。

评论 (1 条评论)

发布
用户头像
Slice本身是有界的,用slice truncate可以免去传start和end两个参数。
2020 年 09 月 30 日 11:21
回复
没有更多了
用go语言实现快排