排序汇总

复杂度稳定性：

排序算法		空间复杂度	时间复杂度			稳定性
	最好		平均	最坏
插入排序	插入排序					稳定
	希尔排序					不稳定
交换排序	冒泡排序					稳定
	快速排序	最坏：				不稳定
选择排序	简单选择排序					不稳定
	堆排序					不稳定
2路归并排序						稳定
基数排序						稳定

比较次数的数量级是否与初始状态有关：

• 插入排序：有关。如果已经有序，那么只需要比较 次，时间复杂度为
• 交换排序：
  • 冒泡排序：有关。如果已经有序，那么只需要进行一趟排序即可，时间复杂度为
  • 快速排序：有关。如果已经有序，那么对应的排序树会是一棵单支树，时间复杂度为
• 选择排序：
  • 简单选择排序：无关。每次选择要把剩余元素全部过一遍。
  • 堆排序：无关。
• 归并排序：无关。
• 基数排序：无关。

哪些情况用哪些排序：

• 外部排序通常采用「归并排序」，因为内存放不下。
• 对中国所有人的生日进行排序，使用「基数排序」最快。
• 平均最好的算法：「快速排序」。
• 为了减少移动耗时，可以使用「链表」作为存储结构。
• 基本有序时，采用「简单插入排序」或者「冒泡排序」。
• 对于 的 种排序算法：
  • 「快速排序」平均性能最好
  • 「堆排序」辅助空间较少，且最坏情况不错
  • 「归并排序」是稳定的，另外两种不稳定