Python----資料結構----排序-----快速排序

Python學習之路，點選有全套Python筆記

快速排序

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列

步驟

• 從數列中挑出一個元素，稱為"基準"（pivot），
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區結束之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
• 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

時間複雜度

• 最優時間複雜度：O(nlogn)
• 最壞時間複雜度：O(n2)
• 穩定性：不穩定

實作

def quick_sort(li, start, end):
    # 分治 一分為二
    # start=end ,證明要處理的資料隻有一個
    # start>end ,證明右邊沒有資料
    if start >= end:
        return
    # 定義兩個遊标，分别指向0和末尾位置
    left = start
    right = end
    # 把0位置的資料，認為是中間值
    mid = li[left]
    while left < right:
        # 讓右邊遊标往左移動，目的是找到小于mid的值，放到left遊标位置
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        # 讓左邊遊标往右移動，目的是找到大于mid的值，放到right遊标位置
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    # while結束後，把mid放到中間位置，left=right
    li[left] = mid
    # 遞歸處理左邊的資料
    quick_sort(li, start, left - 1)
    # 遞歸處理右邊的資料
    quick_sort(li, left + 1, end)
    
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)