3
时间特性： • 时间复杂度为O(nlogn):快速、堆、归并排序，快
速最快，在n较大时，归并较堆更快
• 时间复杂度为O(n2):插入、冒泡、选择排序，插
入最常用，尤其基本有序时，选择记录移动次数最少
• 时间复杂度为O(dn):基数排序(自习)
• 当待排序记录有序时：插入和冒泡可达到O(n)，快 速蜕化到O(n2)；
• 选择、堆和归并排序的时间特性不随关键字分布而 改变
电子科技计算机学院
2. 空间特性：
• 所有的简单排序和堆排序的空间复杂度均为 O(1)；
• 快速排序为O(logn);
• 归并排序和基数排序所需辅助空间最多，其空 间复杂度为O(n).
电子科技计算机学院 ***
5
3. 稳定性：
• 快速排序、希尔排序和堆排序是不稳定的; • 其他排序方法都是稳定的
排序算法
内部排序
插入排序
• 简单插入排序 • 折半插入排序 • 希尔排序
选择排序
• 简单选择排序 • 其他选择排序
归并排序
交换排序
• 冒泡排序 • 快速排序
排序方法比较
排序方法选择主要考虑： • 待排序记录个数n • 记录本身的大小 • 关键字的分布情况 • 对排序稳定性要求
电子科技计算机学院 ***
电子科技计算机学院 ***
6
排序方法 插入排序 选择排序 冒泡排序 快速排序 归并排序 堆排序 基数排序
平均时间
O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(nlogn) O(d*n)
最坏情况
O(n2) O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(d*n)
最好情况
O(n) O(n2) O(n) O(nlogn) O(nlogn) O(nlogn) O(d*n)
辅助空间
O(1) O(1) O(1) O(nlogn) O(n) O(1) O(n)
稳定性
√ √ √ × √ × √
如果待排序数据量很大，不能一次性将 所有数据读入内存，学院