1、各種排序算法的時間復雜度和空間復雜度類別評序方法時間復雜度空間復雜度穩定性平均情況鍛好情況|最壞情況輔助存儲插入宜接插入O(tf)Q(n；fe)O(D定排序Shell排序Ofn1)(O(n)foftf)lo)衛定選擇直接選擇Ofn3)O(n3)0()0(1)冠定排序堆排序O(nlogn)1CKnlogn)1JO(nlog?n)j0(1)不穩定交換泡推序W)|o(n),Ofn2)0(1)穂定排序快速排序O(nlog-,n)| CXnlon)O(nz)OCnlogE不穩定歸并排序OCnlqn)O(nlog;n)CXnlpfen)O(n)穩定基數排序nO(d(r+n)O(d(n+rd)B(d(r+n

2、)；O(rdtn)穩定L1其中冒泡排序加個標志，所以最好情況下是o(n)直接選擇排序：排序過程：、首先在所有數據中經過n-1次比較選出最小的數，把它與第1個數據交換，2、然后在其余的數據內選出排序碼最小的數，與第2個數據交換依次類推，直到所有數據排完為止。在第i趟排序中選出最小關鍵字的數據，需要做 n-i次比較。/冒泡排序，大的數不斷向后冒泡void buddle(vector & nu ms) TOC o 1-5 h z in t le n=nu ms.size();for(int i=0;ile n-1;i+)for(i nt j=O;jnu msj+1)swap( nu msj, nu

3、msj+1);線性排序算法計數排序假設：有n個數的集合，而且n個數的范圍都在Ok(k = O(n)之間運行時間： (n+k)數組加:3*1 2*2+-* 4*-* 0+10+1 1羊屮+J(k1Z*3 -4m-C*32ltnIt1E 2卻 數組G #2+6i7卡S 2.ZP 數組加a0* 0*2#4待排序數組A如圖2.1所示，需要輔助數組B(存儲最后排序結果)，數組C(存儲元素的個數)。基于上 述的假設，數組C的大小為k，Ci表示數組A中元素i(0 = i k) 的個數(如圖2.2所示)，為了保 證計數排序的穩定性，數組 C變化為圖2.3，Ci表示小于或者等于i的個數。代碼如下：1: /*2:

4、輸入：待排序數組A,存儲排序后的數組B,數組A的大小，數組C的大小3:功能：計數排序4: */5: void CountingSort(int A, int B, int len, int k)6: 7:int *Cou ntArr = new in tk;8:int i;9: for (i = 0; i k; i+)10: 11: CountArri = 0;12: 13:14: for (i = 0; i len; i+)15: 16: CountArrAi+;17: 18:19: for (i = 1; i =0; i-)26: 27:BCountArrAi-1 = Ai;28:Coun

5、tArrAi-;29: 30: 9-12行和19-22行的運行時間O (k) ,14-17行和25-29行的運行時間為 O (n)，所以總的運行時間為 0 (2(n+k) =O (n+k)。基數排序基數排序：將所有待比較數值 (正整數)統一為同樣的數位長度,數位較短的數前面補零。然后,從最 低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數列就變成一個有序序列。基數排序分為兩種LSD和MSDLSD(Least significant digital)：最低有效位優先,即從右向左開始排序。MSD(Most significant digital) ：最高有效位優先,即從左往

6、右開始排序。以下是LSD方式的基數排序的偽代碼1: RadixSort(A,d)2: for i - 1 to d3:用穩定的排序算法排列數組A中元素的第i位1261111052-252252f 123T 123-610 252252051352611如圖3:先牌個位，然后十位，最后百位。為數組的某一位排序的時候一定需要穩定的算法。運行時間為 (d(n+k)。在基數排序中排列數組各位的算法是計數排序所以運行時間為 (n+k),又d是數組中數的最大位數。桶排序桶排序：將數組分到有限個桶子內，然后再對桶子里面的序列進行排序，運行時間(n)。桶排序基于一個假設：輸入的數據由隨機過程構成，否則在最壞情

7、況下都分配到一個桶子里面，如果又不滿足計 數排序的假設要求，那么只能使用基于比較的排序算法進行排序，運行時間就退化到Q (nlogn)。排序算法穩定性排序算法穩定性：假設待排序序列中有兩個元素相等，而且在排序前和排序后兩個相等的元素的相對 位置不變，即有a = b,排序前a在b前面，那么排序后，a還是要在b前面。排序算法的穩定性是要 看具體的算法實現，比如一般情況下，直接選擇排序，快速排序，希爾排序，堆排序都不是穩定排序 算法，基數排序，計數排序，歸并排序，插入排序，冒泡排序都是穩定排序算法。快速排序：A = 2，2，1，排序后A = 1，2, 2。希爾排序：A = 1，2, 5, 4，4，7，排序后(k