クイックソートを実装するためのPythonアルゴリズムソート

QUICKSORT(A, p, r) は、クイック ソートのサブルーチンです。分割プログラムを呼び出して配列を分割し、その後 QUICKSORT(A, p, r) を再帰的に呼び出してクイック ソート処理を完了します。クイック ソートの最悪の場合の時間計算量は O(n2) で、通常の時間計算量は O(nlgn) です。最大の時間計算量は、配列が基本的に順序付けられている場合であり、平均的な時間計算量は、配列の数値分布が比較的均一である場合です。通常の状況では、クイック ソートとヒープ ソートの時間計算量は O(nlgn) ですが、クイック ソートの定数項は小さいため、ヒープ ソートよりも優れています。
PARTITION(A, p, r)

コードをコピー コードは次のとおりです:

x ← A[ r]
i ← p - 1
for j ← p to r - 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i] , A[ j])
swap(A[i + 1], A[r])
return i + 1

QUICKSORT(A, p, r)

コードをコピーします コードは次のとおりです:

if p
then q ← PARTITION(A, p, r )
QUICKSORT( A, p, q - 1)
QUICKSORT(A, q + 1, r)

実装:

コードをコピーします コードは次のとおりです:

#!/usr/bin/python
import sys
defpartion(array, p, r):
x = array[r]
i = p - 1
for j in range(p, r):
if (array[j] i+=1
配列[j]、配列[i] = 配列[i]、配列[j]
i+=1
配列[i]、配列[r] = 配列[r]、配列[i]
return i
def Quick_sort (array, p, r):
if p < r:
q =partion(array, p, r)
quick_sort(array, p, q - 1)
quick_sort(array, q + 1, r)
if __name__ == "__main__":
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
Quick_sort(array, 0, len(array) - 1)
配列内の a の場合:
sys.stdout.write("%d " % a)