快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被采用。
該方法的基本思想是：
1．先從數列中取出一個數作為基準數。
2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。
3．再對左右區間重復第二步，直到各區間只有一個數。
現在通過一個實例來說明快排。
比如有一個數組：
|
1
|
6 2 4 5 3 |
第一步：選取一個基準數，不要被這個名詞嚇到了，你可以把它看作是一個比較大小的數，因為排序就是比較大小，
比如我選取最后一個數3為基準數，依次把數組的數和3比較，比3小的放左邊，比3大的放右邊，這樣有如下結果：
|
1
|
2 3 6 4 5 |
第二步：判斷區間個數，經過第一步后左邊區間只有一個數了，沒有數字再和它比較了，因此不需要重復操作，右邊區間還有：
|
1
|
6 4 5 |
重復第一步，選取5作為基準數，得到比較結果：
|
1
|
4 5 6 |
這樣左右兩邊區間都只有一個數了，這就標志著排序完成，最后把所有區間合并就得到排序結果：
|
1
|
2 3 4 5 6 |
|
1
2
3
4
5
6
7
8
9
10
|
def quick_sort(array): less = []; greater = [] if len(array) <= 1: return array pivot = array.pop() for x in array: if x <= pivot: less.append(x) else: greater.append(x) return quick_sort(less) + [pivot] + quick_sort(greater)list = [2,4,2,6,7,8,1] |
|
1
|
print quick_sort(list) |
|
1
|
[1, 2, 2, 4, 6, 7, 8] |
相比C、C#、JAVA之類的是不是簡單多了^.^
TIP：去重的快速排序
如下, 只需要把集合修改為單值元素,這里我們使用Python3來演示:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# -*- coding: utf-8 -*- import random L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] def qsort(L): if len(L)<2: return L pivot_element = random.choice(L) small = [i for i in L if i< pivot_element] #medium = [i for i in L if i==pivot_element] large = [i for i in L if i> pivot_element] return qsort(small) + [pivot_element] + qsort(large) print(qsort(L)) |
輸出:
|
1
|
[2, 3, 4, 5, 6, 8, 9, 10, 11, 17] |
也可以直接使用, 集合(set)進行排序和去重.
|
1
|
mylist = list(set(L)) #集合自動排序字符串 |
