pythonで早列を再論する

今日はpythonで実現された速い列を見て、余分なスペースを消費しましたが、本当に清新で俗っぽいですね...

# -*- coding: UTF-8 -*-

def quicksort(array):
    if(len(array) <= 1):
        return array
    lower = []
    upper = []
    base = array.pop()
    for i in array:
        if i > base:
            upper.append(i)
        else:
            lower.append(i)
    return quicksort(lower) + [base] + quicksort(upper)


print(quicksort([5,2,7,9,12,3,7]))

実行結果:

E:\python_study>python 91.py
[2, 3, 5, 7, 7, 9, 12]

ベースより大きいものは大きな配列に捨てられ、ベースより小さいものは小さな配列に捨てられる.従来の交換位置で実現された高速配列と比較して,余分な空間的複雑さを消費したが,構想は明瞭で簡単すぎた.