8大算法

简介

分类比较

类别	子分类	$T(n)$平均情况	$T(n)$最好情况	$T(n)$最差情况	$S(n)$辅助空间	稳定性	原址排序
插入排序	直接插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	是
	希尔	$O(n^{1.3})$	$O(n)$	$O(n^2)$	$O(1)$	不稳定	是
选择排序	直接选择	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	不稳定	是
	堆排序	$O(n\lg{n})$	$O(n\lg{n})$	$O(n\lg{n})$	$O(1)$	不稳定	是
交换排序	冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	否
	快速排序	$O(n\lg{n})$	$O(n\lg{n})$	$O(n^2)$	$O(n\lg{n}) \leq S(n) \leq O(n)$	不稳定	否
归并排序		$O(n\lg{n})$	$O(n\lg{n})$	$O(n\lg{n})$	$O(n)$	稳定	否
桶（基数）排序		$O(d(r+n))$	$O(d(rd+n))$	$O(d(r+n))$	$O(dr+n)$	稳定	否

基数排序中，$r$表示关键字的基数，$d$表示长度，$n$表示关键字的个数

稳定性：指在排序算法中，相同值的两个元素，在输入数组中先出现的数在输出数组中也先出现

原址排序：基本上不需要额外辅助的的空间，允许少量额外的辅助变量进行的排序。就是在原来的排序数组中比较和交换的排序；

算法选择准则

1. 待排序的记录数目n的大小；
2. 记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3. 关键字的结构及其分布情况；
4. 稳定性要求；

方案选择

设待排序元素的个数为n

1. 当n较大

   1. 快速排序，是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短
   2. 堆排序，如果内存空间允许且要求稳定性的
   3. 归并排序，它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

   当n较大，内存空间允许，且要求稳定性时选择归并排序；

2. n较小时

   1. 直接插入排序，当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数；
   2. 直接选择排序，元素分布有序，如果不要求稳定性，选择直接选择排序；

3. 一般不使用或不直接使用传统的冒泡排序；

4. 基数排序，它是一种稳定的排序算法，但有一定的局限性：

   1. 关键字可分解；
   2. 记录的关键字位数较少，如果密集更好；
   3. 如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序；