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

時間復(fù)雜度

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

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

指數(shù)時間

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

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

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

常數(shù)時間

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

對數(shù)時間

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

常見的具有對數(shù)時間的算法有二叉樹的相關(guān)操作和二分搜索。

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

線性時間

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

一、冒泡算法

基本思想：

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

冒泡排序的示例：

算法實現(xià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] = temp


if __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]

講解:

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

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

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

難點來了，小循環(huán)需要多少次??

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

冒泡排序復(fù)雜度:

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

空間復(fù)雜度: O(1)

穩(wěn)定性: 穩(wěn)定

簡單選擇排序的示例：

二、選擇排序

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

基本思想：

在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。

簡單選擇排序的示例：

算法實現(xiàn):

def select_sort(array):
 for i in range(len(array)-1): # 找出最小的數(shù)放與array[i]交換
 for j in range(i+1, len(array)):
 if array[i] > array[j]:
 temp = array[i]
 array[i] = array[j]
 array[j] = temp


if __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)

選擇排序復(fù)雜度:

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

空間復(fù)雜度: O(1)

穩(wěn)定性: 不穩(wěn)定

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

排序效果：

三、直接插入排序

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

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

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

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

設(shè)監(jiān)視哨是我大一在書上有看過，大家忽視上圖的監(jiān)視哨。

算法實現(xiàn):

import time


def insertion_sort(array):
 for i in range(1, len(array)): # 對第i個元素進行插入，i前面是已經(jīng)排序好的元素
 position = i # 要插入數(shù)的下標
 current_val = array[position] # 把當前值存下來
 # 如果前一個數(shù)大于要插入數(shù)，則將前一個數(shù)往后移，比如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為０或前一個數(shù)比待插入還小時
 array[position] = current_val




if __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]

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

直接插入排序復(fù)雜度:

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

空間復(fù)雜度: O(1)

穩(wěn)定性: 穩(wěn)定

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

四、快速排序

快速排序示例:

算法實現(xiàn):

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](此時應(yīng)該剛存成了key) 跟這個比key大的array[low]進行調(diào)換
 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是會死循環(huán)，此時key=64,　最后的64與開始的64交換，開始的64與本最后的64交換……　無窮無盡

直接插入排序復(fù)雜度:

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

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

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

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

穩(wěn)定性:不穩(wěn)定

快速排序效果：

參考:

Python常用算法學(xué)習(xí)基礎(chǔ)教程

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

c++中八大排序算法

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論