背景：資料結構與演算法是IT相關的工程師一直以來的基礎考察重點，很多經典書籍都是用c++或者java來實作，出于對python編碼效率的喜愛，于是取search了一下python的快排實作，發現大家寫的都比較個性，也所以我也總結下自己理解的python快排實作，
注：本隨筆注重代碼實作，如果是對快速排序無任何接觸的還是先看一下相關的書籍
快速排序簡介：快速排序是突破O(n^2)時間復雜度上界的排序演算法，其平均情況下和最好情況是的時間復雜度都是O(nlogn)，最差情況下的時間復雜度為O(n^2)(最差情況下退化為選擇排序)，空間復雜度為O(logn)
核心思想：
核心為 partition() 函式，該函式每呼叫一次，會產生兩個作用：
例子：待排序陣列為[3,5,1,8,2,4]，呼叫一次該函式后陣列變為[2,1,3,8,5,4]
直接作用：確定待排序陣列上某個位置的值（我們稱這個值為樞軸）；在上例中表現為確定了待排序陣列中索引為2（第3個元素）的值，元素'3'即為樞軸的值
副作用：將待排序資料分為了3個部分，即 [小于等于樞軸的待排序陣列]+樞軸+[大于等于樞軸的待排序陣列]，副作用的貢獻體現在減少了分治的次數
快速排序=對待排序陣列采用分治+遞回的方法呼叫partition()函式
partition()函式的時間復雜度為O(n),分治+遞回呼叫的平均時間復雜度為O(logn),所以總體相乘為O(nlogn)
python代碼實作
第一種實作，partition借助額外的list，所以partition函式的空間復雜度為O(n),因為涉及分治+遞回呼叫，遞回使用的隱含堆疊需要O(logn)的時間復雜度，所以整體空間復雜度為O(nlogn),借助額外的資料結構一般會起到兩個效果：1、降低時間復雜度 或者 2、提高代碼可讀性（易于理解），這里并沒有降低時間復雜度
def quick_sort1(lst): """快速排序""" def partition(lst, left, right): #借助兩個臨時串列存放小于樞軸的元素和大于樞軸的元素 l_list, r_list = [], [] #選取待排序串列的最左元素作為樞軸 pivot_value =https://www.cnblogs.com/tianyadream/p/ lst[left] for i in lst[left+1:right+1]: if i<=pivot_value: l_list.append(i) else: r_list.append(i) #因為是原地排序，所以對原待排序陣列的相應元素進行替換 lst[left:right+1] = l_list+[pivot_value]+r_list return left+len(l_list) def q_sort(lst, left, right): """輔助函式，便于遞回呼叫""" if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
上述實作采用了額外的list，雖然增加了可讀性，但是提高了空間復雜度，所以，可以對其優化，將partition函式的空間復雜度降為O(1)
第二種實作，不借助額外串列
def quick_sort2(lst): """快速排序""" def partition(lst, left, right): #默認選擇串列最左元素作為樞軸 pivot_value =https://www.cnblogs.com/tianyadream/p/ lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 #當右指標對應元素小于樞軸的值，將左右指標對應元素交換，使小于樞軸的值位于樞軸的左側 lst[left], lst[right] = lst[right], lst[left] while left<right and lst[left]<=pivot_value: left+=1 #當左指標對應元素大于樞軸的值，將左右指標對應元素交換，使大于樞軸的值位于樞軸的右側 lst[left], lst[right] = lst[right], lst[left] return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
這里通過元素交換的方式達到了與方法1同樣的效果，所以在很多資料上，快速排序和冒泡排序都被分類為'交換排序'，但有一點要注意，快速排序最差的情況下，會退化為選擇排序而非冒泡排序
針對第二種情況，我們還可以繼續優化，省去不必要的交換，將"交換"優化為“替換”
第三種實作
def quick_sort3(lst): """快速排序""" def partition(lst, left, right): #默認選擇串列最左元素作為樞軸，同時也記錄了left最初對應的元素值 pivot_value =https://www.cnblogs.com/tianyadream/p/ lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 #將left對應的元素替換為right（小于樞軸）對應的元素 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 #將right對應的元素替換為left（大于樞軸）對應的元素 lst[right] = lst[left] #當left和right相等時，使用最初記錄的left對應的元素值替換當前指標的元素 lst[left] = pivot_value #回傳樞軸對應的索引 return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
第三種方案和前兩種一樣，都是將串列的最左元素作為樞軸，這也是導致快速排序最差情況時間復雜度為O(n^2)的原因，比如每次串列的最左元素都為最大值或者最小值，那每次對partition函式的呼叫只起到了直接作用（確定了串列的最左端的最小值或者最右端的最大值），而沒有起到副作用（副作用的目的是減小分治次數）
所以我們可以對樞軸的選取進行優化，優化的目的是使樞軸的選取避開最大值或最小值，盡量靠近中位數，優化的思路有兩種
1、隨機選取
2、選取串列中left, right, (left+right)//2，三個索引位置對應元素居中的元素
由于亂數的生成在編程語言API中的實作也要耗費一定的時間復雜度，所以我們選擇2
第四種實作如下
def quick_sort4(lst): """快速排序""" def partition(lst, left, right): #計算中間索引 mid = (left+right)//2 #將三個元素中大小居中的元素交換至串列的最左側 if lst[left]>lst[mid]: lst[left], lst[mid] = lst[mid], lst[left] if lst[mid]>lst[right]: lst[mid], lst[right] = lst[right], lst[mid] if lst[left]<lst[mid]: lst[left], lst[mid] = lst[mid],lst[left] pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 lst[right] = lst[left] lst[left] = pivot_value return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
經過2~4的優化，我們已經
1）把空間復雜度由O(nlogn)降至O(n),yi
2）并盡量優化了最差情況下的時間復雜度，使其比O(n^2)要好一些
但需要提醒一下，其最佳情況下的時間復雜度依舊使O(nlogn)，而一些簡單排序演算法，如插入排序和優化后的冒泡排序的最優時間復雜度都可以達到O(n)
快排在面對大量資料排序時表現良好，
所以可以進行優化，當待排序資料的元素數量小于某個常數值時采用插入排序，否則使用快速排序
第五種實作
def quick_sort5(lst): """快速排序""" def partition(lst, left, right): #計算中間索引 mid = (left+right)//2 #將三個元素中大小居中的元素交換至串列的最左側 if lst[left]>lst[mid]: lst[left], lst[mid] = lst[mid], lst[left] if lst[mid]>lst[right]: lst[mid], lst[right] = lst[right], lst[mid] if lst[left]<lst[mid]: lst[left], lst[mid] = lst[mid],lst[left] pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 lst[right] = lst[left] lst[left] = pivot_value return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst #取某個常數，待排序元素數量大于該常數時使用快排，否則使用插入排序 if len(lst)>50: q_sort(lst, 0, len(lst)-1) else: #插入排序在此不實作了，大家自行解決 insert_sort(lst) return lst
經過上述優化，我們做到了
1）空間復雜度由O(nlogn)優化至O(logn)
2) 將最差情況下的時間復雜度O(n^2)盡可能提升
3）將時間復雜度的下界提升至O(n)，當然，這已經不是單純的快排了- -！
剛開始寫博客，有不對的地方還望指教~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75816.html
標籤：其他
上一篇：LeetCode：最長回文字串
下一篇：順序存盤佇列操作