兩個簡單排序演算法的Python實現及其時間複雜度分析。

02-01

其實本篇文章重在分析時間複雜度。

先看一個簡單的侏儒排序法，其中只有一個簡單的while循環和一個索引範圍為0到len(seq)-1的索引變數。

# 排序演算法之：侏儒排序法ndef gnomesort(seq):n i = 0n while i < len(seq):n if i == 0 or seq[i-1] <=seq[i]:n i += 1n else:n seq[i], seq[i-1] = seq[i-1], seq[i]n i -=1n

看到這個while和索引範圍，很讓人容易認為他是一個線性時間的演算法，但是不要忘記最後一行有i -= 1語句。

他會從左邊開始掃描，直到找到一個seq[i-1]大於seq[i]的位置i，這是兩個值的順序就錯了，於是else的部分開始生效，然後交換位置之後，繼續向上掃描。

最好的情況是目標序列已經排好序了。這時排序函數只需要將整個序列掃描一遍即可，並不會發現任何錯位，然後便停止了。運算複雜度應為Θ(n).

最壞的情況就是查找並移動這些錯位元素的開銷與其位置形成了正比關係。最糟糕的運行時間應該是1+2+···+n-1，也就是Θ(n2)。

最壞情況也是有可能發生的，於是侏儒排序的運行時間應為Ω(n)與O(n2)來表示，他們分別代表了最好的和最壞的情況。

下面來看一個很著名的歸併排序法：

# 排序演算法之：歸併排序法ndef mergesort(seq):n mid = len(seq)/2n lft, rgt = seq[:mid], seq[mid:]n if len(lft) > 1:n lft = mergesort(lft)n rgt = mergesort(rgt)n res = []n while lft and rgt:n if lft[-1] >= rgt[-1]:n res.append(lft.pop())n else:n res.append(rgt.pop())n res.reverse()n return (lft or rgt) + resn

歸併排序要比侏儒排序稍微複雜一些。儘管你可能不了解演算法工作的前提下，仍然是可以進行分析的。

整體結構為：其輸入(seq)規模為n，有兩重遞歸調用，每次子問題的規模為n/2(儘可能讓其接近整數的規模)。除此之外最後的res.reverse()也包含了部分操作。

這個如果進行推倒，得出遞歸式應該是T(n)=2T(n/2)+Θ(n)，所以歸併排序的運行時間為Θ(nlgn)。

無論輸入情況如何總是這個結果。

當然這個結果你不能說都用歸併排序解決生活中的問題。遇到幾乎是已經排好序的數據，我們可以選用侏儒排序，但是在不確定的情況下，我們仍需要選擇歸併排序來解決問題。

謝謝各位關注.天氣寒冷，大家注意保暖。