前言：前兩天騰訊筆試受到1萬點暴擊，感覺浪費我兩天時間去牛客網做題……這篇博客介紹幾種簡單/常見的排序算法，算是整理下。

時間復雜度

（1）時間頻度一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

（2）時間復雜度在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規律。為此，我們引入時間復雜度概念。 一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度。

指數時間

指的是一個問題求解所需要的計算時間m(n)，依輸入數據的大小而呈指數成長（即輸入數據的數量依線性成長，所花的時間將會以指數成長）

for (i=1; i<=n; i++) x++;for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++;

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。

常數時間

若對于一個算法的上界與輸入大小無關，則稱其具有常數時間，記作時間。一個例子是訪問數組中的單個元素，因為訪問它只需要一條指令。但是，找到無序數組中的最小元素則不是，因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作，或稱時間。但如果預先知道元素的數量并假設數量保持不變，則該操作也可被稱為具有常數時間。

對數時間

若算法的T(n) =O(logn)，則稱其具有對數時間

常見的具有對數時間的算法有二叉樹的相關操作和二分搜索。

對數時間的算法是非常有效的，因為每增加一個輸入，其所需要的額外計算時間會變小。
遞歸地將字符串砍半并且輸出是這個類別函數的一個簡單例子。它需要O（log n）的時間因為每次輸出之前我們都將字符串砍半。 這意味著，如果我們想增加輸出的次數，我們需要將字符串長度加倍。

線性時間

如果一個算法的時間復雜度為O(n)，則稱這個算法具有線性時間，或O(n)時間。非正式地說，這意味著對于足夠大的輸入，運行時間增加的大小與輸入成線性關系。例如，一個計算列表所有元素的和的程序，需要的時間與列表的長度成正比。

一、冒泡算法

基本思想：

在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。

冒泡排序的示例：

算法實現：

def bubble(array): for i in range(len(array)-1): for j in range(len(array)-1-i): if array[j] > array[j+1]: # 如果前一個大于后一個，則交換 temp = array[j] array[j] = array[j+1] array[j+1] = tempif __name__ == "__main__": array = [265, 494, 302, 160, 370, 219, 247, 287, 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304] print("------->排序前<-------") print(array) bubble(array) print("------->排序后<-------") print(array)

輸出:

------->排序前<-------
[265, 494, 302, 160, 370, 219, 247, 287, 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
------->排序后<-------
[82, 83, 160, 219, 247, 258, 265, 287, 291, 302, 304, 319, 345, 354, 370, 405, 423, 469, 494, 497]

講解:

以隨機產生的五個數為例:　li=[354,405,469,82,345]
冒泡排序是怎么實現的?
首先先來個大循環，每次循環找出最大的數，放在列表的最后面。在上面的例子中，第一次找出最大數469，將469放在最后一個，此時我們知道
列表最后一個肯定是最大的，故還需要再比較前面4個數，找出4個數中最大的數405，放在列表倒數第二個......

5個數進行排序，需要多少次的大循環??　當然是4次啦!同理，若有n個數，需n-1次大循環。

現在你會問我: 第一次找出最大數469，將469放在最后一個??怎么實現的??
嗯，（在大循環里）用一個小循環進行兩數比較，首先354與405比較，若前者較大，需要交換數；反之不用交換。
當469與82比較時，需交換，故列表倒數第二個為469；469與345比較，需交換，此時最大數469位于列表最后一個啦!

難點來了，小循環需要多少次??

進行兩數比較，從列表頭比較至列表尾，此時需len(array)-1次!! 但是，嗯，舉個例子吧: 當大循環i為3時，說明此時列表的最后3個數已經排好序了，不必進行兩數比較，故小循環需len(array)-1-3.　即len(array)-1-i

冒泡排序復雜度:

時間復雜度: 最好情況O(n), 最壞情況O(n^2), 平均情況O(n^2)

空間復雜度: O(1)

穩定性: 穩定

簡單選擇排序的示例：

二、選擇排序

The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example

基本思想：

在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然后在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。

簡單選擇排序的示例：

算法實現:

def select_sort(array): for i in range(len(array)-1): # 找出最小的數放與array[i]交換 for j in range(i+1, len(array)): if array[i] > array[j]: temp = array[i] array[i] = array[j] array[j] = tempif __name__ == "__main__": array = [265, 494, 302, 160, 370, 219, 247, 287, 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304] print(array) select_sort(array) print(array)

選擇排序復雜度:

時間復雜度: 最好情況O(n^2), 最壞情況O(n^2), 平均情況O(n^2)

空間復雜度: O(1)

穩定性: 不穩定

舉個例子：序列5 8 5 2 9， 我們知道第一趟選擇第1個元素5會與2進行交換，那么原序列中兩個5的相對先后順序也就被破壞了。

排序效果：

三、直接插入排序

插入排序(Insertion Sort)的基本思想是：將列表分為2部分，左邊為排序好的部分，右邊為未排序的部分，循環整個列表，每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。

插入排序非常類似于整撲克牌。

在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什么時候，左手中的牌都是排好序的。

也許你沒有意識到，但其實你的思考過程是這樣的：現在抓到一張7，把它和手里的牌從右到左依次比較，7比10小，應該再往左插，7比5大，好，就插這里。為什么比較了10和5就可以確定7的位置？為什么不用再比較左邊的4和2呢？因為這里有一個重要的前提：手里的牌已經是排好序的。現在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入。編程對一個數組進行插入排序也是同樣道理，但和插入撲克牌有一點不同，不可能在兩個相鄰的存儲單元之間再插入一個單元，因此要將插入點之后的數據依次往后移動一個單元。

設監視哨是我大一在書上有看過，大家忽視上圖的監視哨。

算法實現:

import timedef insertion_sort(array): for i in range(1, len(array)): # 對第i個元素進行插入，i前面是已經排序好的元素 position = i # 要插入數的下標 current_val = array[position] # 把當前值存下來 # 如果前一個數大于要插入數，則將前一個數往后移，比如5,8,12,7;要將7插入，先把7保存下來，比較12與7，將12往后移 while position > 0 and current_val < array[position-1]: array[position] = array[position-1] position -= 1 else: # 當position為０或前一個數比待插入還小時 array[position] = current_valif __name__ == "__main__": array = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67] print(array) time_start = time.time() insertion_sort(array) time_end = time.time() print("time: %s" % (time_end-time_start)) print(array)

輸出:

[92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
time: 0.0
[6, 8, 43, 55, 67, 67, 77, 84, 85, 92]

如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

直接插入排序復雜度:

時間復雜度: 最好情況O(n), 最壞情況O(n^2), 平均情況O(n^2)

空間復雜度: O(1)

穩定性: 穩定

個人感覺直接插入排序算法難度是選擇/冒泡算法是兩倍……

四、快速排序

快速排序示例:

算法實現:

def quick_sort(array, left, right): ''' :param array: :param left: 列表的第一個索引 :param right: 列表最后一個元素的索引 :return: ''' if left >= right: return low = left high = right key = array[low] # 第一個值，即基準元素 while low < high: # 只要左右未遇見 while low < high and array[high] > key: # 找到列表右邊比key大的值 為止 high -= 1 # 此時直接 把key跟 比它大的array[high]進行交換 array[low] = array[high] array[high] = key while low < high and array[low] <= key: # 找到key左邊比key大的值，這里為何是<=而不是<呢？你要思考。。。 low += 1 # 找到了左邊比k大的值 ,把array[high](此時應該剛存成了key) 跟這個比key大的array[low]進行調換 array[high] = array[low] array[low] = key quick_sort(array, left, low-1) # 最后用同樣的方式對分出來的左邊的小組進行同上的做法 quick_sort(array,low+1, right) # 用同樣的方式對分出來的右邊的小組進行同上的做法if __name__ == '__main__': array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12] print("-------排序前-------") print(array) quick_sort(array, 0, len(array)-1) print("-------排序后-------") print(array)

輸出:

-------排序前-------
[8, 4, 1, 14, 6, 2, 3, 9, 5, 13, 7, 1, 8, 10, 12]
-------排序后-------
[1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 12, 13, 14]

22行那里如果不加＝號，當排序64，77，64是會死循環，此時key=64,　最后的64與開始的64交換，開始的64與本最后的64交換……　無窮無盡

直接插入排序復雜度:

時間復雜度: 最好情況O(nlogn), 最壞情況O(n^2), 平均情況O(nlogn)

下面空間復雜度是看別人博客的，我也不大懂了……改天再研究下。

最優的情況下空間復雜度為：O(logn)；每一次都平分數組的情況

最差的情況下空間復雜度為：O( n )；退化為冒泡排序的情況

穩定性:不穩定

快速排序效果：

參考:

Python常用算法學習基礎教程

視覺直觀感受若干常用排序算法

c++中八大排序算法

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。