各种内部排序算法的比较及应用

内部排序算法的比较

1. 从时间复杂度看:简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为O(n)，且实现过程也较为简单，但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到O(n)，而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的数据都可以达到很高的效率，但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据结构，可以在线性时间内完成建堆，且在 O(nlog₂ⁿ)内完成排序过程。快速排序基于分治的思想虽然最坏情况下的时间复杂度会达到 0(n²)，但快排的平均性能可以达到 O(nlog₂ⁿ)，在实际应用中常常优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 O(nlog₂ⁿ)。
2. 从空间复杂度看:简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需借助常数个辅助空间。快速排序需要借助一个递归工作栈，平均大小为 O(log₂ⁿ)，当然在最坏情况下可能会增长到 O(n)2路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为 O(n)虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。
3. 从稳定性看:插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。平均时间复杂度为 O(nlog₂ⁿ)的稳定排序算法只有归并排序，对于不稳定的排序方法，只需举出一个不稳定的实例即可。对于排序方法的稳定性，读者应能从算法本身的原理上去理解，而不应拘泥于死记硬背.
4. 从过程特征看:采用不同的排序算法，在一次循环或几次循环后的排序结果可能是不同的考研题中经常出现给出一个待排序的初始序列和已经部分排序的序列，问其采用何种排序算法这就要对各类排序算法的过程特征十分熟悉，如冒泡排序和堆排序在每趟处理后都能产生当前的最大值或最小值，而快速排序一趟处理至少能确定一个元素的最终位置等.

各种排序算法的性质

内部排序算法的应用

1. 选取排序方法需要考虑的因素
   1. 待排序的元素数目n。
   2. 元素本身信息量的大小
   3. 关键字的结构及其分布情况
   4. 稳定性的要求
   5. 语言工具的条件，存储结构及辅助空间的大小等。
2. 排序算法小结
3. 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
4. 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
5. 若n较大，则应采用时间复度为0(nlog₂ⁿ)的排序方法:快速排序排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为O(nlog₂ⁿ)，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的因此改进后的归并排序仍是稳定的。
6. 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移因此可以用一棵二叉树来描述比较判定过程，由此可以证明:当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要 O(nlog₂ⁿ)的时间
7. 若n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
8. 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构

题目总结

1. 基数排序不能对float和double类型的实数进行排序。
2. 堆排序和快速排序不是稳定排序方法。
3. 交换类的排序，其趟数和原始序列状态有关，故冒泡排序与初始序列有关。直接插入排序：每趟排序都插入一个元素，所以排序趟数固定为n-1；简单选择排序：每趟都选出一个最小(或最大)的元素，所以排序趟数固定为n-1；基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为d。
4. 插入排序和选择排序的排序趟数始终为n-1，与初始序列无关。
5. 插入排序、选择排序、冒泡排序的原本时间复杂度为O(n²),更换为链式存储后的时间复杂度还是O(n²)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加。
6. 选择一个排序算法时，除算法的时空效率外，还需要考虑的是数据的规模、数据的存储方式、算法的稳定性、数据的初始状态。
7. 直接插入排序和快速排序的特点如下表

	适合初始序列情况	适合元素数量	空间复杂度	稳定性
直接插入排序	大部分元素有序	较少	O(1)	稳定
快速排序	基本无序	较多	O(log2n)	不稳定