快速排序——python資料結構

快速排序

• 取清單的一個元素值作為flag，将數組劃分為兩個部分。flag左邊的值都比它小，右邊的值都比它大。遞歸完成。
• 平均時間複雜度：O(n log(n))
• 最壞時間複雜度：O( n 2 n^2 n2)

def partition(list, left, right):
    temp = list[left]
    while left < right:
        while left < right and list[right] >= temp:
            right -= 1
        list[left] = list[right]
        while left < right and list[left] <= temp:
            left += 1
        list[right] = list[left]
    list[left] = temp
    return left

def quick_sort(list, left, right):
    if left < right:
        index = partition(list, left, right)
        quick_sort(list, left, index-1)
        quick_sort(list, index+1, right)

list = [8, 5, 4, 3, 7, 2, 9]
quick_sort(list, 0, len(list)-1)
print(list)