Sort

2022-11-18
含义
. 将一组杂乱无章的数据按一定规律/关键字顺次排列起来
目的
. 便于查找
分类
1. 内部排序:待排序记录都在内存中
插入类
将无序子序列中的一个或几个记录插入有序序列;包括 直接插入排序折半插入排序希尔排序
交换类
交换无序序列中的记录得到符合特征关键字的记录并加入到有序序列;包括:冒泡排序快速排序
选择类
从无序序列中选择符合特征关键字的记录并加入到有序序列;包括: 简单选择排序树形选择排序堆排序
归并类
归并/合并有序子序列并最终得到有序序列;2-路归并排序
分配类
不需要特征关键字,利用分配和收集完成排序;基数排序
2. 外部排序:待排序记录一部分在内存,一部分在外存;外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多
衡量
. 时间效率:排序速度(比较次数与移动次数)
. 空间效率:占内存辅助空间的大小
. 稳定性:A和B的关键字相等,排序后A、B的先后次序保持不变,则称这种排序算法是稳定的
比较
分类 方法 时间复杂度 空间复杂度 稳定性
平均情况 最坏情况 辅助存储
插入排序 直接插入 O(n2) O(n2) O(1) 稳定
Shell排序 O(n1.3) O(n2) O(1) 不稳定
选择排序 直接选择 O(n2) O(n2) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(1) 不稳定
交换排序 冒泡排序 O(n2) O(n2) O(1) 稳定
快速排序 O(nlog2n) O(n2) O(log2n) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(n) 稳定
基数排序 O((d+n)) O((d+n)) O(r+n) 稳定
练习 Quiz
冒泡排序是稳定的排序方法。(√)
对n个不同的关键字由小到大进行冒泡排序,在下列(B)情况下比较的次数最多。
从小到大排列好的
从大到小排列好的
元素无序
元素基本有序
从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上,这种排序方法称为(C)。
归并排序
冒泡排序
插入排序
选择排序
对数据序列{8,9,10,4,5,6,20,1,2}采用冒泡排序(从后向前次序进行,要求升序),需要进行的趟数至少是(C)。
3
4
5
8
若一个元素序列基本有序,则下列方法较快的是(A)。
直接插入排序
简单选择排序
堆排序
快速排序