Python中怎么實(shí)現(xiàn)快速排序算法,相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策,為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法,通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。
Python實(shí)現(xiàn)快速排序算法
快速排序算法是一種基于交換的高效的排序算法,由C.R.A.Hoare于1962年提出,是一種劃分交換排序。它采用了一種分治的策略,通常稱(chēng)其為分治法(Divide and conquer algorithm)。
分治法的基本思想
將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題,然后將這些子問(wèn)題的解組合為原問(wèn)題的解。
快速排序的基本思想
先找到一個(gè)基準(zhǔn)點(diǎn)(一般指數(shù)組的中部),然后數(shù)組被該基準(zhǔn)點(diǎn)分為兩部分,依次與該基準(zhǔn)點(diǎn)數(shù)據(jù)比較,如果比它小,放左邊;反之,放右邊。
左右分別用一個(gè)空數(shù)組去存儲(chǔ)比較后的數(shù)據(jù)。
最后遞歸執(zhí)行上述操作,直到數(shù)組長(zhǎng)度 <= 1;
動(dòng)畫(huà)圖
代碼實(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: # 從右邊開(kāi)始查找大于參考點(diǎn)的值 while left < right and lists[right] >= key: right -= 1 lists[left] = lists[right] # 這個(gè)位置的值先挪到左邊 # 從左邊開(kāi)始查找小于參考點(diǎn)的值 while left < right and lists[left] <= key: left += 1 lists[right] = lists[left] # 這個(gè)位置的值挪到右邊 # 寫(xiě)回改成的值 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]
看完上述內(nèi)容,你們掌握Python中怎么實(shí)現(xiàn)快速排序算法的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道,感謝各位的閱讀!
本文題目:Python中怎么實(shí)現(xiàn)快速排序算法-創(chuàng)新互聯(lián)
網(wǎng)站路徑:http://jinyejixie.com/article40/dsshho.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供建站公司、網(wǎng)站維護(hù)、虛擬主機(jī)、定制網(wǎng)站、網(wǎng)站制作、企業(yè)網(wǎng)站制作
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容