ソートアルゴリズム(六)---クイックソート(スワップソート)

詳細
直接ソートは交換ソートに属します
基本思想:
1:1つの基準要素(通常は最初の要素または最後の要素)を選択し、列を2つの部分に分け、一部は基準要素より小さく、一部は基準要素より大きい
2:この2つの部分の数列について手順1を繰り返します.
時間の複雑さ:
最良の場合:O(n*logn)
最悪の場合、発泡ソートO(n*n)に劣化する
安定性あんていせい:不安定
pythonコード実装:quick_sort.py

def swap(l, i, j):
    tmp = l[i]
    l[i] = l[j]
    l[j] = tmp

def partition(l, low, high):
    pivo = l[low]               #      
    while(low != high):         #         
        while(low < high and l[high] >= pivo): # high      ，             
            high -= 1
        swap(l, low, high)
        while(low < high and l[low] <= pivo):# low      ，             
            low += 1
        swap(l, low, high)
    return low

def quick_sort(l, low, high):
    if low < high:
        pivokey = partition(l, low, high)
        quick_sort(l, low, pivokey-1)  #         
        quick_sort(l, pivokey+1, high) #         

if __name__ == '__main__':
    l = [57,12,63,29,37,18,34,46,92,87]
    quick_sort(l, 0, 9)
    print('result:' + str(l))