本文用 python 實(shí)現(xiàn)快速排序。

思路

- 假如有一個(gè)序列 [4, 6, 1, 14, 8]，首先要把第一個(gè)數(shù)找到它正確的位置，即它左邊都小于它，右邊均大于它。

1、取出第一個(gè)值 賦值給臨時(shí)變量 target，target = 4 ，取出變量left 記錄左邊下標(biāo)，變量 right 記錄右邊下標(biāo)。

1

2、把 target 與 right 下標(biāo)的值進(jìn)行比較，如果 target 小， 則 right += 1，再重復(fù) 2 的操作。反之將 right 下標(biāo)的值賦值給 left 的值，sort_list[left] = sort_list[right]，然后left += 1 ，執(zhí)行3。

2

3、把 target 與 right 下標(biāo)的值進(jìn)行比較，如果 target 小， 則 right += 1，再重復(fù) 3 的操作。反之將 right 下標(biāo)的值賦值給 left 的值，sort_list[left] = sort_list[right]

3

4、直到 left == right，把 target 賦值給 sort_list[left] ，這時(shí)左邊的數(shù)小于 target ，右邊的數(shù)大于 target。

4

- 然后把 target 左邊的序列和右邊的序列遞歸執(zhí)行上述操作，直到最后，排序完成

代碼

如下：

def quick_sort(sort_list, start, end):
    if start >= end:
        return
     
    # 記錄兩端下標(biāo)
    left = start
    right = end
    # 取第一個(gè)作為目標(biāo)
    target = sort_list[left]
 
    while left < right:
         
        while left < right and target <= sort_list[right]:
            right -= 1
        sort_list[left] = sort_list[right]
 
        while left < right and sort_list[left] < target:
            left += 1
        sort_list[right] = sort_list[left]
 
    sort_list[left] = target
    # 把target兩邊的序列遞歸執(zhí)行
    quick_sort(sort_list, start, left-1)
    quick_sort(sort_list, left+1, end)
 
 
if __name__ == '__main__':
    sort_list = [4, 6, 1, 14, 8]
    quick_sort(sort_list, 0, len(sort_list) - 1)
    print(sort_list)

快速排序是不穩(wěn)定的，平均時(shí)間復(fù)雜度是 O(nlog2n)，最差時(shí)間復(fù)雜度 O(n2)。
----END----