[golang] 数据结构-快速排序
快速排序是个非常经典、高效、常用的排序算法。很多语言标准库里的排序算法都有用到它。
原理 复杂度 代码实现 package main import ( "time" "fmt" "math/rand" ) func main() { var length = 10 var list []int // 以时间戳为种子生成随机数,保证每次运行数据不重复 r := rand.New(rand.NewSource(time.Now().UnixNano())) for i := 0; i < length; i++ { list = append(list,int(r.Intn(50))) } fmt.Println(list) quickSort(list,length-1) fmt.Println(list) } func quickSort(list []int,start,end int) { // 只剩一个元素时就返回了 if start >= end { return } // 标记最左侧元素作为参考 tmp := list[start] // 两个游标分别从两端相向移动,寻找合适的"支点" left := start right := end for left != right { // 右边的游标向左移动,直到找到比参考的元素值小的 for list[right] >= tmp && left < right { right-- } // 左侧游标向右移动,直到找到比参考元素值大的 for list[left] <= tmp && left < right { left++ } // 如果找到的两个游标位置不统一,就游标位置元素的值,并继续下一轮寻找 // 此时交换的左右位置的值,右侧一定不大于左侧。可能相等但也会交换位置,所以才叫不稳定的排序算法 if left < right { list[left],list[right] = list[right],list[left] fmt.Println(list) } } // 这时的left位置已经是我们要找的支点了,交换位置 list[start],list[left] = list[left],tmp // 按支点位置吧原数列分成两段,再各自逐步缩小范围排序 quickSort(list,left-1) quickSort(list,left+1,end) } 运行结果 杂谈遇到最差情况时,上面算法的性能就比较糟糕了,和普通的插入排序差不多。所以为了避免选了个糟糕的支点,可以选择数组中间元素作为对比的标准,或是选3个元素,取中间大小的元素作为参考项。这时可以在一定程度上优化性能。不过最快情况的场景是在太少见,基本可以忽略掉。还有个可优化的点,就是在数据量很少时,快排并不能体现速度优势,反而在二十几个元素以内的排序中比插入排序还慢。所以可以在递归循环里加个判断,如果一侧的元素数量小于某个值(比如20)时直接使用插入排序。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |