Python 3 教程
Python 快速排序
Python3 實(shí)例快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為較小和較大的2個(gè)子序列，然后遞歸地排序兩個(gè)子序列。
步驟為：
- 挑選基準(zhǔn)值：從數(shù)列中挑出一個(gè)元素，稱(chēng)為"基準(zhǔn)"（pivot）;
- 分割：重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）。在這個(gè)分割結(jié)束之后，對(duì)基準(zhǔn)值的排序就已經(jīng)完成;
- 遞歸排序子序列：遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。
遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時(shí)該數(shù)列顯然已經(jīng)有序。
選取基準(zhǔn)值有數(shù)種具體方法，此選取方法對(duì)排序的時(shí)間性能有決定性影響。
實(shí)例
def partition(arr,low,high):
i = ( low-1 ) # 最小元素索引
pivot = arr[high]
for j in range(low , high):
# 當(dāng)前元素小于或等于 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[] --> 排序數(shù)組
# low --> 起始索引
# high --> 結(jié)束索引
# 快速排序函數(shù)
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 ("排序后的數(shù)組:")
for i in range(n):
print ("%d" %arr[i]),
執(zhí)行以上代碼輸出結(jié)果為：
排序后的數(shù)組: 1 5 7 8 9 10其他擴(kuò)展