大佬教程收集整理的这篇文章主要介绍了算法基础之快速排序,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
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
}
以上是大佬教程为你收集整理的算法基础之快速排序全部内容,希望文章能够帮你解决算法基础之快速排序所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。