快速排序的四種python實現(xiàn)（推薦）
快速排序算法，簡稱快排，是最實用的排序算法，沒有之一，各大語言標準庫的排序函數(shù)也基本都是基于快排實現(xiàn)的。
本文用python語言介紹四種不同的快排實現(xiàn)。
1. 一行代碼實現(xiàn)的簡潔版本
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
2. 網(wǎng)上常見的快排實現(xiàn)
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[low]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
quick_sort(array, low, left - 1)
quick_sort(array, left + 1, high)
由于快排是原地排序，因此不需要返回array。
array如果是個列表的話，可以通過len(array)求得長度，但是后邊遞歸調用的時候必須使用分片，而分片執(zhí)行的原列表的復制操作，這樣就達不到原地排序的目的了，所以還是要傳上邊界和下邊界的。
3.《算法導論》中的快排程序
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1
這個版本跟上個版本的不同在于分片過程不同，只用了一層循環(huán)，并且一趟就完成分片，相比之下代碼要簡潔的多了。
4. 用棧實現(xiàn)非遞歸的快排程序
先說兩句題外話，一般意義上的棧有兩層含義，一層是后進先出的數(shù)據(jù)結構棧，一層是指函數(shù)的內存棧，歸根結底，函數(shù)的內存棧的結構就是一個后進先出的棧。匯編代碼中，調用一個函數(shù)的時候，修改的也是堆棧指針寄存器ESP，該寄存器保存的是函數(shù)局部棧的棧頂，另外一個寄存器EBP保存的是棧底。不知道與棧存儲空間相對的堆存儲空間，其組織結構是否也是一個完全二叉樹呢？
高級語言將遞歸轉換為迭代，用的也是棧，需要考慮兩個問題:
1）棧里邊保存什么？
2）迭代結束的條件是什么？
棧里邊保存的當然是需要迭代的函數(shù)參數(shù)，結束條件也是跟需要迭代的參數(shù)有關。對于快速排序來說，迭代的參數(shù)是數(shù)組的上邊界low和下邊界high，迭代結束的條件是low == high。
def quick_sort(array, l, r):
if l >= r:
return
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
stack.extend([low, i, i + 2, high])
另外，當數(shù)組下標為-1時，C++、Java等語言中會報錯，但python中訪問的是最后一個元素，所以如果程序寫錯了，可能其他語言會報錯，但python會輸出一個錯誤的結果。
以上所述是小編給大家介紹的python實現(xiàn)快速排序算法詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
- python快速排序代碼實例
- Python實現(xiàn)的數(shù)據(jù)結構與算法之快速排序詳解
- Python實現(xiàn)快速排序算法及去重的快速排序的簡單示例
- Python實現(xiàn)快速排序和插入排序算法及自定義排序的示例
- 快速排序的算法思想及Python版快速排序的實現(xiàn)示例
- python實現(xiàn)快速排序的示例(二分法思想)
- javascript與Python快速排序實例對比
- python 二分查找和快速排序實例詳解
- Python編程二分法實現(xiàn)冒泡算法+快速排序代碼示例
- Python實現(xiàn)的插入排序，冒泡排序，快速排序，選擇排序算法示例
- Python一行代碼實現(xiàn)快速排序的方法
- Python實現(xiàn)快速排序的方法詳解
相關文章
Python?pickle?二進制序列化和反序列化及數(shù)據(jù)持久化詳解
這篇文章主要介紹了Python?pickle?二進制序列化和反序列化?-?數(shù)據(jù)持久化,模塊?pickle?實現(xiàn)了對一個?Python?對象結構的二進制序列化和反序列化，本文介紹了Pickle的基本用法，需要的朋友可以參考下2024-01-01
matplotlib常見函數(shù)之plt.rcParams、matshow的使用(坐標軸設置)
這篇文章主要介紹了matplotlib常見函數(shù)之plt.rcParams、matshow的使用(坐標軸設置)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
Anaconda指的是一個開源的Python發(fā)行版本,其包含了conda、Python等180多個科學包及其依賴項,下面這篇文章主要給大家介紹了關于在Anaconda安裝Pytorch的詳細步驟,需要的朋友可以參考下2022-07-07
這篇文章主要介紹了Python類中方法getitem和getattr詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08
這篇文章主要介紹了一行代碼python實現(xiàn)文件共享服務器，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
Python操作SQLite數(shù)據(jù)庫過程解析
這篇文章主要介紹了Python操作SQLite數(shù)據(jù)庫過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09
python 實現(xiàn)在一張圖中繪制一個小的子圖方法
今天小編就為大家分享一篇python 實現(xiàn)在一張圖中繪制一個小的子圖方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
在當今的人工智能領域,大型語言模型（LLM）如GPT、BERT等已經成為了研究和應用的熱點,但其訓練和部署成本高昂,且在不同領域或任務間的遷移能力有限,因此,如何有效地實現(xiàn)LLM的模型遷移,成為了一個重要的研究方向,本文將深入探討如何使用Python實現(xiàn)LLM的模型遷2025-02-02
這篇文章主要介紹了python數(shù)據(jù)處理之如何修改索引和行列問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要給大家介紹了關于Python中Get()函數(shù)用法的相關資料,Python get()函數(shù)是一個非常重要的函數(shù),它可以幫助我們從字典中獲取對應鍵的值,避免了因為鍵不存在而發(fā)生錯誤的情況,需要的朋友可以參考下2023-10-10