温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python中怎么实现快速排序算法

发布时间:2021-08-07 15:59:25 来源:亿速云 阅读:117 作者:Leah 栏目:编程语言

Python中怎么实现快速排序算法,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

Python实现快速排序算法

快速排序算法是一种基于交换的高效的排序算法,由C.R.A.Hoare于1962年提出,是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide and conquer algorithm)。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

  • 先找到一个基准点(一般指数组的中部),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。

  • 左右分别用一个空数组去存储比较后的数据。

  • 最后递归执行上述操作,直到数组长度 <= 1;

动画图

Python中怎么实现快速排序算法

代码实现

def quick_sort(lists, left, right):
 '''快速排序'''
 # 跳出递归判断
 if left >= right:
 return lists
 
 # 选择参考点,该调整范围的第1个值
 key = lists[left]
 low = left 
 high = right
 
 # 循环判断直到遍历全部
 while left < right:
 # 从右边开始查找大于参考点的值
 while left < right and lists[right] >= key:
 right -= 1
 lists[left] = lists[right] # 这个位置的值先挪到左边
 
 # 从左边开始查找小于参考点的值
 while left < right and lists[left] <= key:
 left += 1
 lists[right] = lists[left] # 这个位置的值挪到右边
 
 # 写回改成的值
 lists[left] = key
 
 # 递归,并返回结果
 quick_sort(lists, low, left - 1) # 递归左边部分
 quick_sort(lists, left + 1, high) # 递归右边部分
 return lists
numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5]
quick_sort(numbers,0,len(numbers)-1)
assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

看完上述内容,你们掌握Python中怎么实现快速排序算法的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI