您好,登錄后才能下訂單哦!
好程序員Python學(xué)習(xí)路線分享實(shí)現(xiàn)快速排序算法,快速排序算法是一種基于交換的高效的排序算法,由C.R.A.Hoare于1962年提出,是一種劃分交換排序。它采用了一種分治的策略,通常稱其為分治法(Divide and conquer algorithm)。
分治法的基本思想
將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。
快速排序的基本思想
先找到一個(gè)基準(zhǔn)點(diǎn)(一般指數(shù)組的中部),然后數(shù)組被該基準(zhǔn)點(diǎn)分為兩部分,依次與該基準(zhǔn)點(diǎn)數(shù)據(jù)比較,如果比它小,放左邊;反之,放右邊。
左右分別用一個(gè)空數(shù)組去存儲(chǔ)比較后的數(shù)據(jù)。
代碼實(shí)現(xiàn)
def quick_sort(lists, left, right):
'''快速排序'''
# 跳出遞歸判斷
if left >= right:
return lists
# 選擇參考點(diǎn),該調(diào)整范圍的第1個(gè)值
key = lists[left]
low = left
high = right
# 循環(huán)判斷直到遍歷全部
while left < right:
# 從右邊開始查找大于參考點(diǎn)的值
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right] # 這個(gè)位置的值先挪到左邊
# 從左邊開始查找小于參考點(diǎn)的值
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left] # 這個(gè)位置的值挪到右邊
# 寫回改成的值
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]
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。