先列出一些算法複雜度的辨別符号的意思， 最常用的是o，表示算法的上屆，如 2n2 = o(n2 ), 而且有可能是漸進緊确的， 意思是g(n)乘上一個常數系數是可以等于f(n)的，就是所謂的a<=b。而o的差別就是非漸進緊确的，如2n = o(n2 ), o(n2 )确實可以作為2n的上屆， 不過比較大， 就是所謂的a
其他符号表示了下屆，和非漸進緊确的下屆， a>=b, a>b
還有既是上屆也是下屆， 就是a＝b
bubble sort
冒泡排序效率是最低的, 對于list中任意一點, 都必須周遊其後所有元素以找到最小元素, 這個耗費是n
是以對于完整的冒泡算法, 對list中n個點, 算法複雜度就是n2
1 def bubblesort(data):
2 if len(data) < 2: return data
3 for i in range(0, len(data)-1):
4 m = i
5 for j in range(i+1, len(data)):
6 if data[m] > data[j]: m =j
7
8 if m != i:
9 data[i], data[m] = data[m], data[i]
10 return data
insert sort
對于插入的任一個元素, 最差情況是需要周遊它之前的所有元素, 才能找到插入位置. 但這個是最差情況, 一般不需要.
是以他的複雜度同樣是n2 , 但對于普通的排序, 效率要高于冒泡
1 def insertsort(data):
3 for i in range(1,len(data)):
4 print data
5 key = data[i]
6 j = i-1
7 while j >= 0 and key < data[j]:
8 data[j+1] = data[j]
9 j = j-1
10 data[j+1]= key
11 return data
merge sort
這個算法是基于二分法的遞歸算法, 把二分遞歸的過程圖形化, 會形成一個遞歸樹（對分析表示分治算法的遞歸式的複雜度時，遞歸樹方法好用形象）. 樹高為logn, 對于樹的每一層進行并歸操作, 可以看出每層并歸的耗費最大是n, 是以算法複雜度就是nlogn. merge sort的缺點就是, 它不是inplace的, 需要耗費和輸入同樣大小的資料空間.
1 def mergesort(data):
2 length = len(data)
3 if length < 2: return data
4 l = data[:length/2]
5 r = data[length/2:]
6
7 outl = mergesort(l)
8 outr = mergesort(r)
9
10 return merge(outl, outr)
11
12 def merge(l,r):
13 print l,r
14 data = []
15 while len(l)>0 and len(r)>0:
16 if l[0] > r[0]:
17 data.append(l.pop(0))
18 else:
19 data.append(r.pop(0))
20
21 if len(l) >0:
22 data.extend(l)
23 else:
24 data.extend(r)
25 return data
heap sort
堆排序首先是建堆, 建堆就是對所有非葉子節點進行堆化操作, 堆化的最大耗費是logn, 是以建堆的最大耗費是nlogn, 但是其實大部分的節點的高都遠遠沒有logn, 這個可以計算出實際的最大耗費隻有n.
最後排序的耗費n-1次堆化操作, 是以整個的複雜度為nlogn.
堆排序複雜度達到nlogn, 而且是inplace算法.
1 def heapsort(input):
2 output = []
3 buildheap(input)
4 print input
5 while input:
6 i = len(input)-1
7 input[0],input[i] = input[i],input[0]
8 output.append(input.pop())
9 if input:
10 maxheapify(input,0)
11 return output
12
13 def maxheapify(input, i):
14 if i <0:
15 return
16 left = 2*i+1 # because the i from 0, not 1
17 right = 2*i+2
18 largest = i
19 length = len(input)
20 if left < length:
21 if input[i]< input[left]: largest = left
22 if right < length:
23 if input[largest]< input[right]: largest = right
24 if largest != i:
25 input[i], input[largest] = input[largest], input[i]
26 maxheapify(input,largest)
27
28 def buildheap(input):
29 length = len(input)
30 if length < 2: return
31 nonleaf = length/2
32 for i in range(nonleaf,-1,-1):
33 maxheapify(input,i)
quick sort
快排在最差的情況下，即對于已經排好序的序列， 每次劃分都是0和n-1， 這樣的算法複雜度為n2 .這種情況下如果表示成遞歸樹， 樹高為n， 每層partition的耗費是n，是以複雜度為n*n
而在最好情況下就是， 序列為對稱的， 每次為折半劃分， 這個情況和并歸排序一樣， 耗費為nlogn
而在平均情況下， 可以證明是接近最好情況的， 即複雜度為nlogn，原因是任何一種按常數比例進行的劃分都會産生深度為lgn的遞歸樹
1 def partition(data, p, r):
2 i = p-1
3 cmp = data[r]
4 for j in range(p,r):
5 if data[j] < cmp:
6 i = i+1
7 if i <> j: data[i],data[j] = data[j],data[i]
8
9 if (i+1) <> r: data[i+1],data[r] = data[r],data[i+1]
10 return i+1
11 def randompartition(data, p, r):
12 import random
13 i = random.randint(p,r)
14 data[i], data[r] = data[r], data[i]
15 return partition(data, p, r)
16
17 def quicksort(data, p, r):
18 if p < r:
19 q = partition(data, p, r)
20 #q = randompartition(data, p, r)
21 quicksort(data, p, q-1)
22 quicksort(data, q+1, r)
其他排序問題
對于普通的排序算法, 即比較排序算法, 複雜度的下限為nlogn, 不可能比這個更少
對于這個的了解是, 比較排序可以被抽象為決策樹, 對于n個元素可能的排列為n!個, 是以樹的葉子節點有n!個, 對于一個高h的樹, 葉子節點最多有2h 個, 是以可以算出h的下限為nlogn
而對于比較排序而言, 任意兩個元素的順序都要通過一次比較來完成, 是以下限為需要兩兩比較的次數
如果要突破這個下限, 就必須基于某種假設, 而不可能是通用的比較算法.
比如計數排序, 假設輸入由一個小範圍内(小于k)的整數構成, 那排序方法很簡單, 建立一個長度為k的數組a, 周遊輸入, 并把輸入i放入相應的a[i]中. 排序隻要o(n)
如果是桶排序, 假設輸入為均勻分布[0,1), 由一個随機過程産生. 把[0,1)區域均勻劃分為n個子區域, 稱為桶, 然後把輸入分布到各個桶中. 用于輸入是均勻分布的, 每個桶中的輸入一定很少, 那麼先在桶内排序, 然後把各個桶中的元素列出來即可.
本文章摘自部落格園，原文釋出日期：2011-07-04