Python中怎么實現(xiàn)快速排序

今天就跟大家聊聊有關(guān)Python中怎么實現(xiàn)快速排序，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

歸并排序的思路：分裂再合并，在合并的過程中完成排序

快速排序的思路：分揀再分裂

依據(jù)一個“中值”數(shù)據(jù)項，將數(shù)據(jù)表分成兩半，小于中值的一半和大于中值的一半，然后每個部分遞歸地進行快速排序

如果希望左右兩個部分的數(shù)據(jù)項個數(shù)相同，則應(yīng)該找到數(shù)據(jù)表的中位數(shù)，然而找到中位數(shù)需要付出大量的計算開銷，通常選擇將第一個元素作為中值

快速排序代碼思路：

• 設(shè)置第一個元素為中值，從第二個元素開始，分好兩部分元素

• 將第一個元素（中值）放到合適的位置

遞歸三要素：

• 基本結(jié)束條件：數(shù)據(jù)表僅有一個元素，則代表已經(jīng)排序好了

• 縮小規(guī)模：根據(jù)中值，將數(shù)據(jù)表分成兩部分

• 調(diào)用自身：兩部分分別調(diào)用自身進行快速排序

將數(shù)據(jù)表分成兩部分的方法：

設(shè)置左右標號（left和right），將第一個元素作為中值

• 左標（left）從第二個元素開始向右移動，碰到比中值大的則停止

• 右標（right）從末尾開始向左移動，碰到比中值小的則停止

• 判斷左標是否已經(jīng)超過了右標

• 若沒有，交換左右標所指的數(shù)據(jù)

• 若left>right則停止移動，此時right位置就是中值位置，將中值交換到right處
  

完成分裂的過程其實也就完成了排序的一部分工作，由于while循環(huán)要執(zhí)行結(jié)束后才會繼續(xù)后面的程序（即left和right要停止才會結(jié)束），故要先判斷是否已經(jīng) left>right

快速排序過程分為兩部分：分裂和移動

• 分裂過程：若兩部分規(guī)模相當則時間復(fù)雜度O(logn)

• 移動過程：時間復(fù)雜度O(n)

綜上所述，快速排序的時間復(fù)雜度O(nlogn)

并且快速排序運行過程中不需要額外的存儲空間

但是，如果運氣不好，中值所在的分裂點過于偏離中部，造成左右兩部分數(shù)量不平衡，極端情況下，有一部分始終沒有數(shù)據(jù)，這樣時間復(fù)雜度就退化到了O(n^2)

看完上述內(nèi)容，你們對Python中怎么實現(xiàn)快速排序有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。