算法原理

快速排序是一個具有較高性能的排序算法，其主要思想如下：

對數組中的某個元素，確定其在數組中的排序位置，即在其之前的所有元素均小于該元素，在其之后的均大于該元素。對小元素組和大元素組同樣執行該過程，直到全部執行完畢。

每次遞歸確定一個元素的排序位置，核心在于確定大元素組和小元素組。設待處理元素為left，本次循環元素i，大元素組的第一個元素為j：

數組元素可看作該分組 ：

left

less group

(j)—>greater group

i

other

right

初始時刻大小元素組均為空，隨著i不斷后移，逐漸填充兩個元素組。按照如下思路進行處理：

如果array[i] >= array[left], 將i歸入greater_group；如果array[i] < array[left]，將i和j交換。

分組完成后交換array[left]和小元素組最后元素，即可確定array[left]元素在排序數組中的位置。

算法實現

快速排序使用分治思想對劃分的大元素組和小元素組進行分別處理：

def quick_sort(unsorted_array, left = -1, right = -1):

if left == -1 and right == -1:

left = 0

right = len(unsorted_array) - 1

if left >= right:

return

p = quick_sort_partition(unsorted_array, left, right)

quick_sort(unsorted_array, left, p - 1)

quick_sort(unsorted_array, p + 1, right)

注意遞歸返回的條件left >= right，當兩者相等時，待排序數組只有一個元素，因此無需排序；當left > right時，表示待排序數組為空，等價于使用：

if left != p:

quick_sort(unsorted_array, left, p - 1)

if right != p:

quick_sort(unsorted_array, p + 1, right)

快速排序的輔助函數實現如下：

def quick_sort_partition(unsorted_array, left, right):

random_p = random.randint(left, right)

unsorted_array[left], unsorted_array[random_p] = unsorted_array[random_p], unsorted_array[left]

v = unsorted_array[left]

last_of_less_group = left

for i in range(left, right + 1):

if(v > unsorted_array[i]):

last_of_less_group += 1

unsorted_array[last_of_less_group], unsorted_array[i] = unsorted_array[i], unsorted_array[last_of_less_group]

unsorted_array[left], unsorted_array[last_of_less_group] = unsorted_array[last_of_less_group], unsorted_array[left]

return last_of_less_group

其中包含了一個典型優化，隨機選擇待處理元素。這是由于對于近乎有序數組，快速排序劃分的兩個子數組一長一短，這種不平衡的劃分會增加時間復雜度，最壞情況會達到$ O(N^2) $。

之后按照前述方式確定元素在排序數組中的位置。除此之外，還可以使用挖坑填數的方式從兩端向中間尋找位置，詳見下文兩路快排。

算法優化

快排有諸多優化方式：

隨機選擇待處理元素。

在元素較少的時候，使用插入排序作為代替，較少遞歸開銷。

雙路快排，通過打亂相等元素，解決重復元素造成劃分不平衡的問題。

三路快排，通過明確劃分出相等元素，進一步解決上述問題。

雙路快排

對于前文介紹的單路快排，如果數組中存在大量重復元素，在某輪遞歸處理中，將會出現大量array[left]==array[i]的情況，這些相等的數值會被放到大元素組，從而造成劃分的不平衡。為了解決這個問題，采用如下思路：

從數組左端開始構造小元素組，從右端構造大元素組，直到兩邊都遇到不屬于該元素組的元素，將這兩個元素交換。其中等于array[left]（待確定排序位置的元素）的情況也進行交換。

通過這種方式，等于array[left]的元素被盡可能地分散到兩個分組中。

例如，對于數組[1, 2, 2, 3, 1, 1, 1, 1, 0, 0, 0, 1, 1, 2, 2]。

雙路交換后變為[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 3, 2, 2, 2, 2]，返回的劃分點位置為6(0為起始)。

如果為單路交換，結果為[0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2], 返回的劃分點位置為3。

如果將下述雙路快排中unsorted_array[i] < v和unsorted_array[j] > v改為unsorted_array[i] <= v和unsorted_array[j] >= v，此時對于相等的情況不交換。結果為[0, 0, 0, 1, 1, 1, 1, 1, 3, 2, 2, 1, 1, 2, 2], 返回的劃分點位置為3。

顯然，后兩種情況都產生了不平衡的劃分。

def quick_sort_partition_two_way(unsorted_array, left, right):

random_p = random.randint(left, right)

unsorted_array[left], unsorted_array[random_p] = unsorted_array[random_p], unsorted_array[left]

v = unsorted_array[left]

i = left + 1

j = right

while True:

while i <= right and unsorted_array[i] < v:

i += 1

while j >= left + 1 and unsorted_array[j] > v:

j -= 1

if i >= j:

break

unsorted_array[i], unsorted_array[j] = unsorted_array[j], unsorted_array[i]

i += 1

j -= 1

unsorted_array[left], unsorted_array[j] = unsorted_array[j], unsorted_array[left]

return j

注意，while i <= right and unsorted_array[i] < v:這一行不可以先判斷元素大小再判斷數組越界，這樣會出現數組訪問越界錯誤，當前寫法利用了“與”運算如果前面為False則不再考慮后面的特性。

三路快排

上述雙路快排只是盡可能的解決了重復元素的問題，三路快排通過顯式的將數組劃分為三組，有效解決了重復元素的問題。劃分的三組為大于array[left]，小于array[left]，等于array[left]。其主要思路與前述兩個快排類似：

每輪遞歸中，對于當前元素i，如果小于目標，放到左邊的less_group，如果大于目標，放到右邊的greater_group，如果等于目標，放到中間。之后對兩邊的大小分組繼續遞歸，直到排序完成。

使用python的partition函數實現如下：

def quick_sort_partition_three_way(unsorted_array, left, right):

random_p = random.randint(left, right)

unsorted_array[left], unsorted_array[random_p] = unsorted_array[random_p], unsorted_array[left]

last_of_less_group = left

first_of_greater_group = right + 1

v = unsorted_array[left]

i = left + 1

while i < first_of_greater_group:

if unsorted_array[i] < v:

unsorted_array[last_of_less_group + 1], unsorted_array[i] = unsorted_array[i], unsorted_array[last_of_less_group + 1]

i += 1

last_of_less_group += 1

elif unsorted_array[i] > v:

unsorted_array[i], unsorted_array[first_of_greater_group - 1] = unsorted_array[first_of_greater_group - 1], unsorted_array[i]

first_of_greater_group -= 1

else:

i += 1

unsorted_array[left], unsorted_array[last_of_less_group] = unsorted_array[last_of_less_group], unsorted_array[left]

return last_of_less_group, first_of_greater_group

上述實現較為簡單，其中需要注意的地方在于unsorted_array[i] > v的情況時，不需要進行i += 1，這是由于換過來的元素大小不定，需要在當前位置繼續比較。而對于unsorted_array[i] < v的情況，交換過來的array[last_of_less_group + 1]一定等于v，因此可以前往下一個元素。

算法測試

本文涉及代碼均通過正確性測試。以下是性能測試結果：

創建測試數組

對于快速排序：

100000大小數組耗時:0.484760s

1000000大小數組耗時:7.085851s

100000大小隨機范圍較小數組耗時: **stack overflow**

100000大小近乎有序數組耗時:0.386866s

.

對于雙路快速排序：

100000大小數組耗時:0.327692s

1000000大小數組耗時:4.167595s

100000大小隨機范圍較小數組耗時:0.328271s

100000大小近乎有序數組耗時:0.257662s

.

對于三路快速排序：

100000大小數組耗時:0.467874s

1000000大小數組耗時:6.011800s

100000大小隨機范圍較小數組耗時:0.032722s

100000大小近乎有序數組耗時:0.472250s

.

對于歸并排序：

100000大小數組耗時:0.684923s

1000000大小數組耗時:7.055477s

100000大小隨機范圍較小數組耗時:0.613237s

100000大小近乎有序數組耗時:0.473848s

.

----------------------------------------------------------------------

Ran 4 tests in 37.741s

OK

首先值得注意的是，如果對10000大小隨機范圍[0-3]的數組進行單路快排，會出現棧溢出。此時重復元素過多，劃分過于不平衡，遞歸次數過多。

整體而言，快速排序具有很好的性能，尤其雙路快排擁有最快的性能，但三路快排對存在大量重復元素有著更好的性能，因此被許多編程語言作為默認排序方法。另外，Python的默認排序方法為TimeSort，其性能更為優秀。

算法復雜度

時間復雜度為$ O(Nlog(N)) $，空間復雜度為$ O(1) $。

有趣的實現

來源于網絡的一則單行快排python實現，可以看作上文單路快排，且不含優化的版本。

quicksort = lambda l: quicksort([i for i in l[1:] if i < l[0]]) + [l[0]] + quicksort([j for j in l[1:] if j >= l[0]]) if l else []

總結

以上是生活随笔為你收集整理的python实现快速排序算法_基础算法：快速排序（python实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。