好程序员Python学习路线分享实现快速排序算法「建议收藏」

好程序员Python学习路线分享实现快速排序算法「建议收藏」好程序员Python学习路线分享实现快速排序算法快速排序算法是一种基于交换的高效的排序算法,由C.R.A.Hoare于1962年提出,是一种划分

欢迎大家来到IT世界,在知识的湖畔探索吧!

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

好程序员Python学习路线分享实现快速排序算法「建议收藏」

分治法的基本思想

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

快速排序的基本思想

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

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

– 最后递归执行上述操作,直到数组长度 <= 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]

“`

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/22897.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信