八十一、最快最優(yōu)的快速排序和優(yōu)化

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

快速排序

不久前，我在牛客中看到這樣一個笑話，面試官讓他寫一個快速排序，結(jié)果他寫了一個冒泡排序，雖說不是計(jì)算機(jī)專業(yè)的，還一直說沒有寫錯，都不知道面試官為什么這么PASS。其實(shí)，一共有十大排序算法，最快最穩(wěn)定的就是快速排序，簡稱快排。

quicksort 可以說是應(yīng)用最廣泛的排序算法之一，它的基本思想是分治法?；A(chǔ)的快速排序算法思想很簡單，核心就是一句話：找到基準(zhǔn)值的位置。

具體的過程其實(shí)和把大象裝進(jìn)冰箱這個問題一樣，都可以分成三步：

「第一步，選擇一個值作為基準(zhǔn)值?！?/strong>

「第二步，找到基準(zhǔn)值的位置，并將小于基準(zhǔn)值的元素放在基準(zhǔn)值的前面，大于基準(zhǔn)值的元素放在基準(zhǔn)值的后面?！?/strong>

「第三步，對基準(zhǔn)值的左右兩側(cè)遞歸地進(jìn)行這個過程?！?/strong>

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ]為例，選擇一個支點(diǎn), index= (L+R)/2 = (0+7)/2=3, 支點(diǎn)的值 pivot = arr[index] = arr[3] = 6，接下來需要把 arr 中小于 6 的移到左邊，大于 6 的移到右邊，最后然后對基準(zhǔn)值的左右兩側(cè)遞歸地進(jìn)行這個過程。

快速排序最好用遞歸的代碼實(shí)現(xiàn)，代碼簡單可讀性前。

def?quick_sort(b):
????"""快速排序"""
????if?len(b)?2:
????????return?arr
????#?選取基準(zhǔn)，隨便選哪個都可以，選中間的便于理解
????mid?=?arr[len(b)?//?2]
????#?定義基準(zhǔn)值左右兩個數(shù)列
????left,?right?=?[],?[]
????#?從原始數(shù)組中移除基準(zhǔn)值
????b.remove(mid)
????for?item?in?b:
????????#?大于基準(zhǔn)值放右邊
????????if?item?>=?mid:
????????????right.append(item)
????????else:
????????????#?小于基準(zhǔn)值放左邊
????????????left.append(item)
????return?quick_sort(left)?+?[mid]?+?quick_sort(right)

def?quicksort(array):
??if?len(array)?2:
????#?基本情況下，具有0或1個元素的數(shù)組是已經(jīng)“排序”的
????return?array
??else:
????#?基準(zhǔn)選取不同
????pivot?=?array[0]
????#?小于基準(zhǔn)值的所有元素的子數(shù)組
????less?=?[i?for?i?in?array[1:]?if?i?<=?pivot]
????#?大于基準(zhǔn)值的所有元素的子數(shù)組
????greater?=?[i?for?i?in?array[1:]?if?i?>?pivot]
????return?quicksort(less)?+?[pivot]?+?quicksort(greater)

print(quicksort([10,?5,?2,?3]))

快排優(yōu)化

快排優(yōu)化的方法就是：「合理選擇pivot?！?/strong>。我們知道，如果基準(zhǔn)值選取不合理的話，快速排序的時間復(fù)雜度有可能達(dá)到 這個量級，也就是退化成和選擇排序、插入排序等算法一樣的時間復(fù)雜度。只有當(dāng)基準(zhǔn)值每次都能將排序區(qū)間中的數(shù)據(jù)平分時，時間復(fù)雜度才是最好情況下的 O(nlogn)。

關(guān)于基準(zhǔn)值選取的一個優(yōu)化策略，「三點(diǎn)取中法?！?/strong>

謂三點(diǎn)取中法，就是每一輪取排序區(qū)間的頭、尾和中間元素這三個值，然后把它們排序以后的中間值作為本輪的基準(zhǔn)值。調(diào)整要選取的這三個值的位置。

我們就以上圖為例，假設(shè)本輪的三個值分別為 2、9、7，中間值是 7，所以，本輪的基準(zhǔn)值就是 7。

快排優(yōu)化：「更快地分區(qū)」?？焖倥判虻淖龇ㄊ菑淖笙蛴乙来闻c pivot 比較，做交換，這樣做其實(shí)效率并不高。

舉個簡單的例子，一個數(shù)組 [2, 1, 3, 1, 3, 1, 3]，選第一個元素作為 pivot 是2，每次發(fā)現(xiàn)比2小的數(shù)會引起一次交換，一共三次。

然而，直觀來說，其實(shí)只要將第一個3和最后一個1交換就可以達(dá)到這三次交換的效果。所以更理想的分區(qū)方式是從「兩邊向中間遍歷」的雙向分區(qū)方式，而不是從左到右，當(dāng)然前提是基準(zhǔn)值選擇數(shù)組的中位數(shù)。

具體快速排序優(yōu)化的代碼如下所示。

'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公眾號：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/21
'''
def?quick_sort(nums,?start,?end):
????if?start?>=?end:
????????return
????pivot?=?nums[start]??#?基準(zhǔn)值
????low?=?start??#?左指針
????high?=?end??#?右指針
????while?low?????????while?low?=?pivot:
????????????high?-=?1
????????nums[low]?=?nums[high]

????????while?low?????????????low?+=?1
????????nums[high]?=?nums[low]
????nums[low]?=?pivot
????quick_sort(nums,?start,?low?-?1)
????quick_sort(nums,?low?+?1,?end)

if?__name__?==?'__main__':
????nums?=?[54,?26,?93,?17,?77,?31,?44,?55,?20]
????quick_sort(nums,?0,?len(nums)?-?1)
????print(nums)

快速排序的名字起的是簡單粗暴，因?yàn)橐宦牭竭@個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了，而且Python內(nèi)置的sorted就是快速排序。

雖然 Worst Case 的時間復(fù)雜度達(dá)到了O(n2)，比如說順序數(shù)列的快排。但是就是優(yōu)秀，在大多數(shù)情況下都比平均時間復(fù)雜度為 O(n logn)的排序算法表現(xiàn)要更好，，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?