常用的排序算法的时间复杂度和空间复杂度
常用的排序算法的時間復(fù)雜度和空間復(fù)雜度
?
?
| ??????????????? ? ????????????????????????? |
1、時間復(fù)雜度
（1）時間頻度 一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機(jī)運行測試才能知道。但我們不可能也沒有必要對每個算法都上機(jī)測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。
（2）時間復(fù)雜度 在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。
在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為O(1),另外，在時間頻度不相同時，時間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O(n2)。 按數(shù)量級遞增排列，常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。 2、空間復(fù)雜度 與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量。記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時間復(fù)雜度類似，不再贅述。
（3）漸進(jìn)時間復(fù)雜度評價算法時間性能 主要用算法時間復(fù)雜度的數(shù)量級(即算法的漸近時間復(fù)雜度)評價一個算法的時間性能。
2、類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。
空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機(jī)存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地/"進(jìn)行的，是節(jié)省存儲的算法，如這一節(jié)介紹過的幾個算法都是如此；有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時，將占用較多的存儲單元，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。
如當(dāng)一個算法的空間復(fù)雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時，可表示為O(1)；當(dāng)一個算法的空間復(fù)雜度與以2為底的n的對數(shù)成正比時，可表示為0(10g2n)；當(dāng)一個算法的空I司復(fù)雜度與n成線性比例關(guān)系時，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機(jī)器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應(yīng)實參變量的地址，以便由系統(tǒng)自動引用實參變量。
?
常用的內(nèi)部排序方法有：交換排序（冒泡排序、快速排序）、選擇排序（簡單選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、基數(shù)排序（一關(guān)鍵字、多關(guān)鍵字）。
一、冒泡排序：
?? 1.基本思想：
兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。
2.排序過程：
設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
二、快速排序（Quick Sort）
??? 1.基本思想：
在 當(dāng)前無序區(qū)R[1..H]中任取一個數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I-1]和 R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即 R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時，分別對它們進(jìn)行上述的劃分過 程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。
??? 2.排序過程：
??? 【示例】：
??? 初始關(guān)鍵字 [49 38 65 97 76 13 27 49］
??? 第一次交換后 ［27 38 65 97 76 13 49 49］
??? 第二次交換后 ［27 38 49 97 76 13 65 49］
??? J向左掃描，位置不變，第三次交換后 ［27 38 13 97 76 49 65 49］
??? I向右掃描，位置不變，第四次交換后 ［27 38 13 49 76 97 65 49］
??? J向左掃描 ［27 38 13 49 76 97 65 49］
?? （一次劃分過程）
??? 初始關(guān)鍵字 ［49 38 65 97 76 13 27 49］
??? 一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
??? 二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
??? 三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序結(jié)果 13 27 38 49 49 65 76 97
三、簡單選擇排序
??? 1.基本思想：
每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
??? 2.排序過程：
【示例】：
??? 初始關(guān)鍵字 [49 38 65 97 76 13 27 49]
??? 第一趟排序后 13 ［38 65 97 76 49 27 49]
??? 第二趟排序后 13 27 ［65 97 76 49 38 49]
??? 第三趟排序后 13 27 38 [97 76 49 65 49]
??? 第四趟排序后 13 27 38 49 [49 97 65 76]
??? 第五趟排序后 13 27 38 49 49 [97 97 76]
??? 第六趟排序后 13 27 38 49 49 76 [76 97]
??? 第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序結(jié)果 13 27 38 49 49 76 76 97
四、堆排序(Heap Sort)
??? 1.基本思想：
??? 堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。
??? 2.堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：
??????? Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
??? 堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個 堆，它對應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等 于其孩子的關(guān)鍵字，則稱之為大根堆。
??? 3.排序過程：
??? 堆排序正是利用小根堆（或大根堆）來選取當(dāng)前無序區(qū)中關(guān)鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當(dāng)前無 序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐 步向前擴(kuò)大到整個記錄區(qū)。
【示例】：對關(guān)鍵字序列42，13，91，23，24，16，05，88建堆
?
五、直接插入排序(Insertion Sort)
1. 基本思想：
每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
2. 排序過程：
【示例】：
[初始關(guān)鍵字] [49] 38 65 97 76 13 27 49
???? J=2(38) [38 49] 65 97 76 13 27 49
???? J=3(65) [38 49 65] 97 76 13 27 49
???? J=4(97) [38 49 65 97] 76 13 27 49
???? J=5(76) [38 49 65 76 97] 13 27 49
???? J=6(13) [13 38 49 65 76 97] 27 49
???? J=7(27) [13 27 38 49 65 76 97] 49
???? J=8(49) [13 27 38 49 49 65 76 97]
六、希爾排序
1.排序思想：
先 取一個小于n的證書d1作為第一個增量，把文件的全部記錄分成d1組。所有距離為d1的倍數(shù)的記錄放在同一組中。先在各組內(nèi)進(jìn)行直接插入排序，然后取第二 個增量d2<d1重復(fù)上述的分組和排序，直到所取的增量dt=1，即所有記錄放在同一組中進(jìn)行直接插入排序為止。該方法實際上是一種分組插入方法。
2.排序過程：
[初始關(guān)鍵字] 72 28 51 17 96 62 87 33 45 24
d1=n/2=5????? 62 28 33 17 24 72 87 51 45 96
d2=d1/2=3??? 17 24 33 62 28 45 87 51 72 96
d3=d2/2=1???? 17 24 28 33 45 51 62 72 87 96
七、歸并排序
1.排序思想：
設(shè)兩個有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個局部的暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回R[low..high]中。
?????? 2.排序過程：
【示例】：
初始關(guān)鍵字??? [46][38][56][30][88][80][38]
第一趟歸并后[38 46][30 56][80 88][38]
第二趟歸并后[30 38 46 56][38 80 88]
最終歸并結(jié)果[30 38 38 46 56 80 88]
八、基數(shù)排序
1.排序思想：
（1）根據(jù)數(shù)據(jù)項個位上的值，把所有的數(shù)據(jù)項分為10組；
（2）然后對這10組數(shù)據(jù)重新排列：把所有以0結(jié)尾的數(shù)據(jù)排在最前面，然后是結(jié)尾是1的數(shù)據(jù)項，照此順序直到以9結(jié)尾的數(shù)據(jù)，這個步驟稱為第一趟子排序；
（3）在第二趟子排序中，再次把所有的數(shù)據(jù)項分為10組，但是這一次是根據(jù)數(shù)據(jù)項十位上的值來分組的。這次分組不能改變先前的排序順序。也就是說，第二趟排序之后，從每一組數(shù)據(jù)項的內(nèi)部來看，數(shù)據(jù)項的順序保持不變；
（4）然后再把10組數(shù)據(jù)項重新合并，排在最前面的是十位上為0的數(shù)據(jù)項，然后是10位為1的數(shù)據(jù)項，如此排序直到十位上為9的數(shù)據(jù)項。
（5）對剩余位重復(fù)這個過程，如果某些數(shù)據(jù)項的位數(shù)少于其他數(shù)據(jù)項，那么認(rèn)為它們的高位為0。
2.排序過程
【示例】
初始關(guān)鍵字???? 421 240 035 532 305 430 124
第一趟排序后[240 430] [421] [532] [124] [035 305]
第二趟排序后(305) (421 124) (430 532 035) (240)
最后排序結(jié)果(035) (124) (240) (305) (421 430) (532)
?
?
本文為轉(zhuǎn)載內(nèi)容? 出處忘了、、、、、尷尬
轉(zhuǎn)載于:https://www.cnblogs.com/xuxinstyle/p/9603240.html
總結(jié)
以上是生活随笔為你收集整理的常用的排序算法的时间复杂度和空间复杂度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C++Primer笔记-----day0
- 下一篇： STL---string