Quicksort是一個(gè)分而治之的算法抑淫，它根據(jù)主元把一個(gè)大數(shù)組分成2個(gè)小數(shù)組：其中1個(gè)數(shù)組的元素要比主元小鞠抑，另一個(gè)要比主元大跷叉。Quicksort至今依然是一個(gè)常用的排序算法左敌，如果算法實(shí)現(xiàn)好的情況下瘾蛋，它的速度要比merge sort 和 heapsort快2到3倍。一個(gè)有效實(shí)現(xiàn)地Quicksort 并不是一個(gè)stable sort矫限，即相等元素的相對順序不能被保證哺哼。Quicksort 也可以在一個(gè)數(shù)組上進(jìn)行原址排序。數(shù)學(xué)分析表明叼风，quicksort排序n個(gè)元素平均需要O(nlogn)O(nlogn) 比較取董，在最壞的情況下，它需要O(n2)O(n2)次比較无宿，雖然這樣的行為不常見茵汰。
Quicksort的步驟
Quicksort主要包含以下3步：
- 從數(shù)組中取出一個(gè)元素，叫做主元（pivot）
- 重排序數(shù)組懈贺，使得所有小于pivot的元素在它前面经窖，所有大于pivot的元素在它后面，等于pivot的元素放在哪面都行梭灿。這樣的劃分以后画侣，pivot的位置已經(jīng)排好了。這個(gè)過程叫做partition操作
- 遞歸地應(yīng)用步驟2到小于pivot的子數(shù)組和大于pivot的子數(shù)組
在上面的步驟中堡妒，遞歸的base case是數(shù)組的大小為0或1配乱，因?yàn)檫@樣的數(shù)組已經(jīng)有序，不需要再排序皮迟。我們有很多方式來選擇pivot搬泥，不同地方式會(huì)對算法的性能有很大地影響。
$
def partition(a, l, r):
i = l
j = r
while i < j:
while a[i] < a[l] and i < j:
i += 1
while a[j] > a[l] and i < j:
j -= 1
if i < j:
temp = a[i]
a[i] = a[j]
a[j] = temp
temp = a[l]
a[l] = a[j]
a[j] = temp
return j
def quick_sort(a, l, r):
if l < r:
index = partition(a, l, r)
sort(a, l, index - 1)
sort(a, index + 1, r)
return a
a = [2, 4, 5, 3, 8]
quick_sort(a, 0, 4)