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

時(shí)間復(fù)雜度

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

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

指數(shù)時(shí)間

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

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

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

常數(shù)時(shí)間

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

對(duì)數(shù)時(shí)間

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

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

對(duì)數(shù)時(shí)間的算法是非常有效的，因?yàn)槊吭黾右粋€(gè)輸入，其所需要的額外計(jì)算時(shí)間會(huì)變小。
遞歸地將字符串砍半并且輸出是這個(gè)類別函數(shù)的一個(gè)簡(jiǎn)單例子。它需要O（log n）的時(shí)間因?yàn)槊看屋敵鲋拔覀兌紝⒆址嘲搿?這意味著，如果我們想增加輸出的次數(shù)，我們需要將字符串長(zhǎng)度加倍。

線性時(shí)間

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

一、冒泡算法

基本思想：

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

冒泡排序的示例：

算法實(shí)現(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]: # 如果前一個(gè)大于后一個(gè)，則交換
 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]

講解:

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

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

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

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

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

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

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

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

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

簡(jiǎ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ù)中，選出最?。ɑ蛘咦畲螅┑囊粋€(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。

簡(jiǎ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ù)雜度:

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

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

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

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

排序效果：

三、直接插入排序

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

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

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

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

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

算法實(shí)現(xiàn):

import time


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

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

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

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

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

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

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

四、快速排序

快速排序示例:

算法實(shí)現(xiàn):

def quick_sort(array, left, right):
 '''
 :param array:
 :param left: 列表的第一個(gè)索引
 :param right: 列表最后一個(gè)元素的索引
 :return:
 '''
 if left >= right:
 return

 low = left
 high = right
 key = array[low] # 第一個(gè)值，即基準(zhǔn)元素

 while low < high: # 只要左右未遇見
 while low < high and array[high] > key: # 找到列表右邊比key大的值 為止
 high -= 1
 # 此時(shí)直接 把key跟 比它大的array[high]進(jìn)行交換
 array[low] = array[high]
 array[high] = key

 while low < high and array[low] <= key: # 找到key左邊比key大的值，這里為何是<=而不是<呢？你要思考。。。
 low += 1
 # 找到了左邊比k大的值 ,把a(bǔ)rray[high](此時(shí)應(yīng)該剛存成了key) 跟這個(gè)比key大的array[low]進(jìn)行調(diào)換
 array[high] = array[low]
 array[low] = key

 quick_sort(array, left, low-1) # 最后用同樣的方式對(duì)分出來的左邊的小組進(jìn)行同上的做法
 quick_sort(array,low+1, right) # 用同樣的方式對(duì)分出來的右邊的小組進(jìn)行同上的做法


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行那里如果不加＝號(hào)，當(dāng)排序64，77，64是會(huì)死循環(huán)，此時(shí)key=64,　最后的64與開始的64交換，開始的64與本最后的64交換……　無窮無盡

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

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

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

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

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

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

快速排序效果：

參考:

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

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

c++中八大排序算法

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

最新評(píng)論