NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

快速排序演算法,簡稱快排,是最實用的排序演算法,沒有之一,各大語言標準庫的排序函式也基本都是基於快排實現的。

本文用python語言介紹四種不同的快排實現。

1. 一行程式碼實現的簡潔版本

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. 網上常見的快排實現

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)求得長度,但是後邊遞迴呼叫的時候必須使用分片,而分片執行的原列表的複製操作,這樣就達不到原地排序的目的了,所以還是要傳上邊界和下邊界的。

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

這個版本跟上個版本的不同在於分片過程不同,只用了一層迴圈,並且一趟就完成分片,相比之下程式碼要簡潔的多了。

4. 用棧實現非遞迴的快排程式

先說兩句題外話,一般意義上的棧有兩層含義,一層是後進先出的資料結構棧,一層是指函式的記憶體棧,歸根結底,函式的記憶體棧的結構就是一個後進先出的棧。彙編程式碼中,呼叫一個函式的時候,修改的也是堆疊指標暫存器ESP,該暫存器儲存的是函式區域性棧的棧頂,另外一個暫存器EBP儲存的是棧底。不知道與棧儲存空間相對的堆儲存空間,其組織結構是否也是一個完全二叉樹呢?

高階語言將遞迴轉換為迭代,用的也是棧,需要考慮兩個問題:

1)棧裡邊儲存什麼?

2)迭代結束的條件是什麼?

棧裡邊儲存的當然是需要迭代的函式引數,結束條件也是跟需要迭代的引數有關。對於快速排序來說,迭代的引數是陣列的上邊界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])

另外,當陣列下標為-1時,C 、Java等語言中會報錯,但python中訪問的是最後一個元素,所以如果程式寫錯了,可能其他語言會報錯,但python會輸出一個錯誤的結果。

    

相關文章

程式語言 最新文章