好程序員Python學(xué)習(xí)路線分享實現(xiàn)快速排序算法,快速排序算法是一種基于交換的高效的排序算法,由C.R.A.Hoare于1962年提出,是一種劃分交換排序。它采用了一種分治的策略,通常稱其為分治法(Divide and conquer algorithm)。
分治法的基本思想
將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。
快速排序的基本思想
-
先找到一個基準點(一般指數(shù)組的中部),然后數(shù)組被該基準點分為兩部分,依次與該基準點數(shù)據(jù)比較,如果比它小,放左邊;反之,放右邊。
-
左右分別用一個空數(shù)組去存儲比較后的數(shù)據(jù)。
- 最后遞歸執(zhí)行上述操作,直到數(shù)組長度 <= 1;
代碼實現(xiàn)
def quick_sort(lists, left, right):
'''快速排序'''
# 跳出遞歸判斷
if left >= right:
return lists
# 選擇參考點,該調(diào)整范圍的第1個值
key = lists[left]
low = left
high = right
# 循環(huán)判斷直到遍歷全部
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
# 遞歸,并返回結(jié)果
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]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
