各种排序算法的时间复杂度和空间复杂度

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