Python クイックソート
Python3 例クイックソートは分割統治法（Divide and conquer）戦略を使用して、シーケンス（list）をより小さい部分列とより大きい部分列の2つの部分列に分割し、その後、2つの部分列を再帰的にソートします。
手順は次のとおりです：
- ピボット値の選択：数列から1つの要素を選び出し、「基準」（pivot）と呼びます;
- 分割：数列を並べ替え、基準値より小さいすべての要素を基準の前に置き、基準値より大きいすべての要素を基準の後ろに置きます（基準値と等しい数はどちら側でも構いません）。この分割が終わると、基準値のソートは完了します;
- 部分列の再帰的ソート：基準値より小さい要素の部分列と基準値より大きい要素の部分列を再帰的にソートします。
再帰の最下部の判断条件は、数列のサイズが0または1であることです。その場合、その数列は明らかにすでにソートされています。
基準値の選択にはいくつかの具体的な方法があります。この選択方法はソートの時間性能に決定的な影響を与えます。
例
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その他の拡張