十大排序算法（四）--- 快速排序

快速排序算法采用的是分治法的思想(Divide and Conquer), 它把一個待排序的數(shù)組，以某個元素或者稱為基準(zhǔn)(這里記為PIVOT)為界，分為兩個子數(shù)組，比PIVOT小的全部移到到PIVOT左邊，比PIVOT大的全部移動到PIVOT右邊。再分別對以PIVOT分開的兩個子數(shù)組重復(fù)該過程，直到無法再分。

快速排序正常情況下時間復(fù)雜度為O(nlogn)。最壞情況下為O(n^2)。最壞情況發(fā)生在每次排序都需要移動所有剩下待排序的元素，這種情況雖然很少發(fā)生，但是為了避免這樣的情況可以采用隨機(jī)選擇PIVOT元素的方法來預(yù)防。下面描述算法的實(shí)現(xiàn)步驟：

1. 隨機(jī)的從待排序數(shù)組中選擇一個元素作為PIVOT
2. 將所有比PIVOT小的數(shù)放到PIVOT的左邊，比PIVOT大的數(shù)放到PIVOT的右邊。跟PIVOT一樣大的數(shù)，放到左右都可以。這個步驟稱為Partition。這樣以PVIOT為界分成了左右兩個子數(shù)組。
3. 對#2分成兩個子數(shù)組遞歸進(jìn)行#1~#3操作，直到排序完成。

假設(shè)我們要對A[5, 3, 6, 1, 2, 8]留個數(shù)進(jìn)行排序，下圖展示了排序的過程。

快速排序過程展示

絕大多數(shù)情況下，快速排序是高效的，但是快速排序不是穩(wěn)定的。下面是python的代碼實(shí)現(xiàn)。有興趣的同學(xué)，也可以用其它編程語言嘗試實(shí)現(xiàn)一下。

import random

A = [5, 3, 6, 1, 2, 8]

def quick_sorting(data, left, right):

if left >= right : return

mark = random.randint(left, right)

data[left], data[mark] = data[mark], data[left]

mark = left

tmp = data[left]

for i in range(left 1, right 1):

if data[i] < tmp:

mark = 1

data[i], data[mark] = data[mark], data[i]

data[left], data[mark] = data[mark], data[left]

quick_sorting(data, left, mark-1)

quick_sorting(data, mark 1, right)

def main():

right=len(A)-1

left = 0

#Ascending

quick_sorting(A, left, right)

print(A)

if __name__=='__main__':

main()

將上面的代碼保存到一個文本文件，后綴名修改為.py?？梢杂胮ython解釋器執(zhí)行一下，會輸出如下結(jié)果：

可以看到，排序正確。