Python實現(xiàn)快速排序的方法詳解
本文實例講述了Python實現(xiàn)快速排序的方法。分享給大家供大家參考,具體如下:
說起快排的Python實現(xiàn),首先談一下,快速排序的思路:
1、取一個參考值放到列表中間,初次排序后,讓左側(cè)的值都比他小,右側(cè)的值,都比他大。
2、分別對左側(cè)和右側(cè)的部分遞歸第1步的操作
實現(xiàn)思路:
- 兩個指針left,right分別指向列表的第一個元素和最后一個元素,然后取一個參考值,默認為第一個列表的第一個元素list[0],稱為K
- 然后left指向的值先和參考值K進行比較,若list[left]小于或等于K值,left就一直向右移動,left+1,直到移動到大于K值的地方,停住
- right指向的值和參考值K進行比較,若list[right]大于K值,right就一直向左移動,right-1,直到移動到小于K值的地方,停住
- 此時,left和right若還沒有相遇,即left還小于right,則二者指向的值互換
- 若已經(jīng)相遇則說明,第一次排序已經(jīng)完成,將list[right]與list[0]的值進行互換,進行之后的遞歸
編程實現(xiàn):
#快排的主函數(shù),傳入?yún)?shù)為一個列表,左右兩端的下標(biāo) def QuickSort(list,low,high): if high > low: #傳入?yún)?shù),通過Partitions函數(shù),獲取k下標(biāo)值 k = Partitions(list,low,high) #遞歸排序列表k下標(biāo)左側(cè)的列表 QuickSort(list,low,k-1) # 遞歸排序列表k下標(biāo)右側(cè)的列表 QuickSort(list,k+1,high) def Partitions(list,low,high): left = low right = high #將最左側(cè)的值賦值給參考值k k = list[low] #當(dāng)left下標(biāo),小于right下標(biāo)的情況下,此時判斷二者移動是否相交,若未相交,則一直循環(huán) while left < right : #當(dāng)left對應(yīng)的值小于k參考值,就一直向右移動 while list[left] <= k: left += 1 # 當(dāng)right對應(yīng)的值大于k參考值,就一直向左移動 while list[right] > k: right = right - 1 #若移動完,二者仍未相遇則交換下標(biāo)對應(yīng)的值 if left < right: list[left],list[right] = list[right],list[left] #若移動完,已經(jīng)相遇,則交換right對應(yīng)的值和參考值 list[low] = list[right] list[right] = k #返回k值 return right list_demo = [6,1,2,7,9,3,4,5,10,8] print(list_demo) QuickSort(list_demo,0,9) print(list_demo)
運行結(jié)果:
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
PS:這里再為大家推薦一款關(guān)于排序的演示工具供大家參考:
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python列表(list)操作技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
- python 實現(xiàn)多維數(shù)組(array)排序
- python實現(xiàn)堆排序的實例講解
- 使用python實現(xiàn)希爾、計數(shù)、基數(shù)基礎(chǔ)排序的代碼
- Python將列表中的元素轉(zhuǎn)化為數(shù)字并排序的示例
- Python函數(shù)參數(shù)類型及排序原理總結(jié)
- 利用python實現(xiàn)冒泡排序算法實例代碼
- python快速排序的實現(xiàn)及運行時間比較
- python常用排序算法的實現(xiàn)代碼
- python list多級排序知識點總結(jié)
- python字典排序的方法
- Python 使用多屬性來進行排序
- python中字典按鍵或鍵值排序的實現(xiàn)代碼
- 10個python3常用排序算法詳細說明與實例(快速排序,冒泡排序,桶排序,基數(shù)排序,堆排序,希爾排序,歸并排序,計數(shù)排序)
相關(guān)文章
Python數(shù)據(jù)結(jié)構(gòu)與算法之跳表詳解
跳表是帶有附加指針的鏈表,使用這些附加指針可以跳過一些中間結(jié)點,用以快速完成查找、插入和刪除等操作。本節(jié)將詳細介紹跳表的相關(guān)概念及其具體實現(xiàn),需要的可以參考一下2022-02-02windows下cx_Freeze生成Python可執(zhí)行程序的詳細步驟
這篇文章主要介紹了windows下cx_Freeze生成Python可執(zhí)行程序的詳細步驟,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-10-10