算法基础之快速排序
2021/7/17 14:38:48
本文主要是介绍算法基础之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序(QuickSort)
基本思想
1、选定Pivot中心轴( 选取一个数作为基准数,一般取第一个数) 2、将大于Pivot的数字放在Pivot的右边 3、将小于Pivot的数字放在Pivot的左边 4、分别对左右子序列重复前三步操作,直到各区间只有一个数
排序过程解析
例:[7,3,29,5,9] 第一次: 选取第一个元素7为Pivot 定义左右指针,分别指向第一个和最后一个元素 将右指针指向元素9与7比较 比元素7大,所以9还是放到右指针位置不动,右指针向前移动一位 将右指针指向元素5与7比较 比元素7小,所以5移动到左指针位置,左指针向后移动一位 将左指针指向元素3与7比较 比元素3小,所以3还是放到左指针位置不动,左指针向后移动一位 将左指针指向元素29与7比较 比元素7大,所以29移动到右指针位置,右指针向前移动一位 左右指针相遇,第一次排序结束: 结果 = [5、3、7、29、9] 递: 左 [5、3],右 [29、9] 重复上面步骤... 左 [3、5],右 [9、29] 归: [3,5,7,9,29]
复杂度
最好时间复杂度为:O(nlogn) 最差 O(n^2) 空间复杂度 log(n) 快排是一种非稳定排序
代码解析
func QuickSort(list []int,begin int,end int) { if begin < end{ // 切分排序 loc := partition(list,begin,end) // 递归排序左边 QuickSort(list,begin,loc-1) // 递归排序右边 QuickSort(list,loc+1,end) } } // 将数组进行快速排序,返回排序后的中间元素索引 func partition(list []int,begin int,end int) int { // list[being]为基准元素,用来比较 // 定义左右指针 left := begin + 1 right := end // 当左右两指针重合时结束 for left < right{ // 判断左指针元素是否大于基准元素,如果大于基准元素则左右指针元素交换位置,右指针--,否则左指针++ if list[left] > list[begin] { list[left],list[right] = list[right],list[left] right-- }else{ left++ } } // 当前左右指针重合,指向元素左边的都是小于基准元素的,右边的都是大于基准元素的 // 这里需要判断,指向元素是否比基准元素大,如果大于等于基准元素,那么left左移一格,将基准元素与比他小的元素替换位置 // 如果小于基准元素,那么不需要移动,直接将指向元素和基准元素替换位置即可 if list[left] >= list[begin]{ left-- } list[begin],list[left] = list[left],list[begin] return left }
这篇关于算法基础之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么修改Kafka的JVM参数?-icode9专业技术文章分享
- 2024-12-23线下车企门店如何实现线上线下融合?
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转,哪款办公软件可助力风险评估?
- 2024-12-23优化库存,提升效率:医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担!轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘,为何是团队成长的核心环节?
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动:电商复盘从基础到进阶!
- 2024-12-23从数据到客户:跨境电商如何通过销售跟踪工具提升营销精准度?