快速排序算法使用了分治思想。分治是說(shuō)如果一個(gè)比較難的問(wèn)題不好解決，我們可以嘗試把它分解成若干個(gè)簡(jiǎn)單的同類子問(wèn)題，依次求解各個(gè)子問(wèn)題，再將子問(wèn)題的解組合起來(lái)得到原問(wèn)題的解。
快排的思想是：
- 在數(shù)據(jù)集中找一個(gè)元素作為基準(zhǔn)值 (pivot), 一般取第一個(gè)就行
- 所有比基準(zhǔn)值小的元素放到基準(zhǔn)值的左邊，大于等于基準(zhǔn)值的元素放到基準(zhǔn)值的右邊
- 對(duì)左右子集重復(fù)上面兩部操作，直到數(shù)據(jù)集為空或數(shù)據(jù)集中只剩下一個(gè)元素
如對(duì) 6, 2, 8, 3, 12, 7 進(jìn)行排序
第一步以 6 作為基準(zhǔn)值，分出左右2個(gè)子集
[2, 3] [6] [8, 12, 7]
左右子集遞歸操作
[] [2] [3] [6] [7] [8] [12]
合并結(jié)果集
2 3 6 7 8 12
def quick_sort(l):
if len(l) <= 1: # 基線條件：空數(shù)組或只有一個(gè)元素的數(shù)組本來(lái)就有序直接返回
return l
pivot = l[0] # 取第一個(gè)元素為基準(zhǔn)值
left = [x for x in l[1:] if x < pivot] # 小于基準(zhǔn)值的數(shù)放到左邊
right = [x for x in l[1:] if x >= pivot] # 大于等于基準(zhǔn)值的數(shù)放到右邊
# 對(duì)左右子集遞歸調(diào)用快速排序，最后將結(jié)果集拼接
return quick_sort(left) + [pivot] + quick_sort(right)
l = [6, 2, 8, 3, 12, 7]
print(l)
l = quick_sort(l)
print(l)
遞歸必須有退出條件，這里退出條件就是空數(shù)組或只有一個(gè)元素的數(shù)組，這兩種情況我們是知道怎么排序的，它們本來(lái)就有序。
快速排序是一種不穩(wěn)定的排序算法
快速排序是最快的排序算法之一，算法平均時(shí)間復(fù)雜度是 O(nlog(n)), 最壞時(shí)間復(fù)雜度是 O(n^2)
