Python 快速排序

Document 對象參考手冊 Python3 實例

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然後遞歸地排序兩個子序列。

步驟為：

  • 挑選基準值：從數列中挑出一個元素，稱為"基準"（pivot）;
  • 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成;
  • 遞歸排序子序列：遞歸地將小於基準值元素的子序列和大於基準值元素的子序列排序。

遞歸到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序。

選取基準值有數種具體方法，此選取方法對排序的時間性能有決定性影響。

實例

def partition(arr,low,high): i = ( low-1 ) # 最小元素索引 pivot = arr[high] for j in range(low , high): # 當前元素小於或等於 pivot if arr[j] <= pivot: i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return ( i+1 ) # arr[] --> 排序數組 # low --> 起始索引 # high --> 結束索引 # 快速排序函數 def quickSort(arr,low,high): if low < high: pi = partition(arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr,0,n-1) print ("排序後的數組:") for i in range(n): print ("%d" %arr[i]),

執行以上代碼輸出結果為：

排序後的數組:
1
5
7
8
9
10

Document 對象參考手冊 Python3 實例