- 排序趟数和原始序列有关 ：交换类（冒泡 快速）
- 关键字比较次数和原始序列无关 ：简单选择排序和折半插入排序
- 经过一趟排序，能保证一个关键字到达其最终位置：交换类（冒泡，快速）和选择类（简单选择，堆排序）
- 借助于“比较”进行排序的算法，在最坏情况下的时间复杂度至少为O（nlog2n）
| 所有内排序总结 北航考研911 数据结构 |
内部排序
排序原理
交换类排序
排序趟数和原始序列有关
冒泡排序
排序总趟数
和原始序列有关
稳定性
稳定
时间复杂度
O(n²)
空间复杂度
O(1)
快速排序
待排序列越接近有序，本算法效率越低
排序总趟数
和原始序列有关
稳定性
不稳定
时间复杂度
O（nlog2n）
空间复杂度
O（log2n）
最好情况下，待排序列越无序，时间复杂度 O（nlog2n），算法效率越高
最坏情况下，待排序列越有序，时间复杂度O（ ），算法效率越低
排序趟数和初始序列有关
选择类排序
简单选择排序
排序总趟数
主算法中两次循环执行次数和初始序列没有关系
n-1趟
稳定性
基于交换的简单排序（顺序表）
不稳定
基于插入的简单排序（链表）
稳定
时间复杂度
O（n²）
空间复杂度
O（1）
堆排序
稳定性
不稳定
时间复杂度
O（nlog2n）
空间复杂度
O（1）
特点及使用情况
关键字较多，典型例子是从10000个关键字中选出当前10个最小的，如果，关键字数较少，不推荐用堆排序
插入类排序
直接插入排序
稳定性
稳定
时间复杂度
O（n²）
空间复杂度
O（1）
折半插入排序
稳定性
稳定
时间复杂度
O（n²）
空间复杂度
O（1）
希尔排序
稳定性
不稳定
时间复杂度
O（nlog2n）
空间复杂度
O（1）
稳定性
不稳定
记忆技巧：
情绪不稳定，快 些 选一 堆 好友来搞基吧！
快速
希尔
选择（基于交换）
堆
快速排序
希尔排序
选择排序
堆排序
稳定
时间复杂度
O（nlog2n）
记忆技巧：
军训时，教官说：“快 些以nlog2n的速度 归 队”
快速
希尔
归并
堆
快速排序
希尔排序
归并排序
堆排序
O（n²）
空间复杂度
O（log2n）
快速排序
O（1）
O（n）
归并排序