本文接上一篇博客python實現的八大排序算法part1，將繼續使用python實現八大排序算法中的剩余四個：快速排序、堆排序、歸并排序、基數排序
5、快速排序
快速排序是通常被認為在同數量級（O(nlog2n)）的排序方法中平均性能最好的。
算法思想：
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據并排序，使a[x]排在數據的第k位，并且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然后采用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。
python代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def quick_sort(list): little = [] pivotList = [] large = [] # 遞歸出口 if len(list) <= 1: return list else: # 將第一個值做為基準 pivot = list[0] for i in list: # 將比基準小的值放到less數列 if i < pivot: little.append(i) # 將比基準大的值放到more數列 elif i > pivot: large.append(i) # 將和基準相同的值保存在基準數列 else: pivotList.append(i) # 對less數列和more數列繼續進行快速排序 little = quick_sort(little) large = quick_sort(large) return little + pivotList + large |
下面這段代碼出自《Python cookbook 第二版的三行實現python快速排序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:[email protected]desc:python實現八大排序算法'''lst = [65,568,9,23,4,34,65,8,6,9]def quick_sort(list): if len(list) <= 1: return list else: pivot = list[0] return quick_sort([x for x in list[1:] if x < pivot]) + \ [pivot] + \ quick_sort([x for x in list[1:] if x >= pivot]) |
運行測試結果截圖：
好吧，還有更精簡的語法糖，一行完事：
quick_sort = lambda xs : ( (len(xs) <= 1 and [xs]) or [ quick_sort( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + quick_sort( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]
若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準記錄，即將排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。快速排序是一個不穩定的排序方法。
在改進算法中,我們將只對長度大于k的子序列遞歸調用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復雜度有所降低，且當k取值為 8 左右時,改進算法的性能最佳。
6、堆排序（Heap Sort）
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
優點 : 效率高
缺點：不穩定
堆的定義下：具有n個元素的序列 （h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項（大頂堆）。完全二 叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。
算法思想：
初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲序，使之成為一個 堆，這時堆的根節點的數最大。然后將根節點與堆的最后一個節點交換。然后對前面(n-1)個數重新調整使之成為堆。依此類推，直到只有兩個節點的堆，并對 它們作交換，最后得到有n個節點的有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。
python代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def adjust_heap(lists, i, size):# 調整堆 lchild = 2 * i + 1;rchild = 2 * i + 2 max = i if i < size / 2: if lchild < size and lists[lchild] > lists[max]: max = lchild if rchild < size and lists[rchild] > lists[max]: max = rchild if max != i: lists[max], lists[i] = lists[i], lists[max] adjust_heap(lists, max, size)def build_heap(lists, size):# 創建堆 halfsize = int(size/2) for i in range(0, halfsize)[::-1]: adjust_heap(lists, i, size)def heap_sort(lists):# 堆排序 size = len(lists) build_heap(lists, size) for i in range(0, size)[::-1]: lists[0], lists[i] = lists[i], lists[0] adjust_heap(lists, 0, i) print(lists) |
結果示例：
7、歸并排序
算法思想：
歸并（Merge）排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] print(result) return resultdef merge_sort(lists):# 歸并排序 if len(lists) <= 1: return lists num = int(len(lists) / 2) left = merge_sort(lists[:num]) right = merge_sort(lists[num:]) return merge(left, right) |
程序結果示例：
8、桶排序/基數排序(Radix Sort)
優點：快，效率最好能達到O(1)
缺點：
1.首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數組的空間開銷，一個存放待排序數組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數組就要至少m個空間。
2.其次待排序的元素都要在一定的范圍內等等。
算法思想：
是將陣列分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞回方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數據分組，放在一個個的桶中，然后對每個桶里面的在進行排序。
例如要對大小為[1..1000]范圍內的n個整數A[1..n]排序
首先，可以把桶大小設為10，這樣就有100個桶了，具體而言，設集合B[1]存儲[1..10]的整數，集合B[2]存儲 (10..20]的整數，……集合B[i]存儲( (i-1)*10, i*10]的整數，i = 1,2,..100。總共有 100個桶。
然后，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應的桶B[j]中。 再對這100個桶中每個桶里的數字排序，這時可用冒泡，選擇，乃至快排，一般來說任 何排序法都可以。
最后，依次輸出每個桶里面的數字，且每個桶中的數字從小到大輸出，這 樣就得到所有數字排好序的一個序列了。
假設有n個數字，有m個桶，如果數字是平均分布的，則每個桶里面平均有n/m個數字。如果
對每個桶中的數字采用快速排序，那么整個算法的復雜度是
O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)
從上式看出，當m接近n的時候，桶排序復雜度接近O(n)
當然，以上復雜度的計算是基于輸入的n個數字是平均分布這個假設的。這個假設是很強的 ，實際應用中效果并沒有這么好。如果所有的數字都落在同一個桶中，那就退化成一般的排序了。
python代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''import mathlst = [65,56,9,23,84,34,8,6,9,54,11]#因為列表數據范圍在100以內，所以將使用十個桶來進行排序def radix_sort(lists, radix=10): k = int(math.ceil(math.log(max(lists), radix))) bucket = [[] for i in range(radix)] for i in range(1, k+1): for j in lists: gg = int(j/(radix**(i-1))) % (radix**i) bucket[gg].append(j) del lists[:] for z in bucket: lists += z del z[:] print(lists) return lists |
程序運行測試結果：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/lockey23/article/details/77773771
