基本思想
通過一趟排序?qū)⑿蛄蟹指顬閮刹糠?，其中一部分的?shù)據(jù)比另外一部分的所有數(shù)據(jù)都要小，然后按照同樣的規(guī)則對這兩個(gè)序列進(jìn)行同樣的操作，知道最后被分割的序列有且只有一個(gè)。
在程序中，如何實(shí)現(xiàn)一部分的數(shù)據(jù)比另外一部分的數(shù)據(jù)都要小，這里需要定義一個(gè)基數(shù)來作為比較，比這個(gè)基數(shù)小的分為一部分，比這個(gè)基數(shù)大的分為另外一部分。
示例
** 對序列[6 1 2 7 9 3 4 5 10 8]進(jìn)行第一趟分割 **
- 在序列中找一個(gè)數(shù)作為基數(shù)，為了方便，一邊選擇最左邊或最右邊的數(shù)，我們這里選擇最左邊的6作為基數(shù)。
- 我們假設(shè)有一個(gè)男同學(xué)站左邊的1上面，女同學(xué)站在右邊的8上面。
-
然后女同學(xué)先往左邊走（因?yàn)檫x擇最左邊的6作為基數(shù)，為了在最后一步去基數(shù)交換，所以必須先讓女生走），如果走到比基數(shù)6小的位置則停下；然后男生往右邊走，走到比基數(shù)6大的位置停下；然后交換位置下面的數(shù)據(jù)。（以下圖片都來自于《啊哈！算法》）
Paste_Image.png -
重復(fù)第三步一次
Paste_Image.png -
重復(fù)第三步第二次
Paste_Image.png - 第一趟后的結(jié)果 [3 1 2 5 4 6 9 7 10 8]，然后把基數(shù)6前面和后面的分割為兩個(gè)序列進(jìn)行同樣的操作。最后可完成升序排序。
python實(shí)現(xiàn)算法
#!/usr/bin/python
# encoding: utf-8
# 快速排序
def quickSort(alist, left, right):
# 判斷結(jié)束遞歸
if left >= right:
return 0
# base為基數(shù)
base, i, j = alist[left], left, right
while i < j:
# 因?yàn)榛鶖?shù)是最左邊的數(shù)，所以要先從右邊往左找
while (alist[j] >= base and i < j):
j -= 1
while (alist[i] <= base and i < j):
i += 1
# 找到一個(gè)比基數(shù)大，一個(gè)比基數(shù)小后，交換
alist[i], alist[j] = alist[j], alist[i]
# 最后與基數(shù)交換
alist[left], alist[i] = alist[i], alist[left]
# 遞歸處理分割后的序列
quickSort(alist, left, i - 1)
quickSort(alist, i + 1, right)
elem = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
quickSort(elem, 0, len(elem) - 1)
print(elem) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
時(shí)間復(fù)雜度
最壞的情況為N的平方
平均時(shí)間復(fù)雜度O(nlogn)
