快速排序python實現總結
- 2020 年 3 月 10 日
- 筆記
背景：數據結構與演算法是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 = 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 = 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 = 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)，當然，這已經不是單純的快排了- -！
剛開始寫部落格，有不對的地方還望指教~~~
