Python程式設計：排序算法之快速排序

快速排序

取一個元素p（第一個元素）,使元素p歸位

清單被p分成兩部分，左邊都比p小，右邊都比p大

遞歸完成排序

算法關鍵點

• 整理
• 遞歸（遞歸深度）

排序方法	最好情況	一般情況	最壞情況
	O(nlogn)		O(n^2)
冒泡排序	O(n)

代碼實作

import random

# 分區函數
def partition(lst, left, right):
    tmp = lst[left]
    while left<right:
        while left<right and lst[right]>=tmp:
            right -= 1
        lst[left] = lst[right]

        while left<right and lst[left]<=tmp:
            left += 1
        lst[right] = lst[left]

    lst[left] = tmp
    return left

# 快速排序
def quick_sort(lst, left, right):
    if left < right:
        mid = partition(lst, left, right)
        quick_sort(lst, left, mid-1)
        quick_sort(lst, mid+1, right)

lst = list(range(10))
random.shuffle(lst)
quick_sort(lst, 0, len(lst)-1)
print(lst)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]