第13周内排序第7讲-內排序的比较.pdf
排序方法排序方法 时间复杂度时间复杂度 空间复杂度空间复杂度稳定性稳定性 平均情况平均情况最坏情况最坏情况最好情况最好情况 直接插入排序直接插入排序O(n2)O(n2)O(n)O(1)稳定稳定 折半插入排序折半插入排序O(n2)O(n2)O(nlog2n)O(1)稳定稳定 希尔排序希尔排序O(n1.3)O(1) 不稳定不稳定 冒泡排序冒泡排序O(n2)O(n2)O(n)O(1) 稳定稳定 快速排序快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定不稳定 简单选择排序简单选择排序O(n2)O(n2)O(n2)O(1) 不稳定不稳定 堆排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1) 不稳定不稳定 二路归并排序二路归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定 基数排序基数排序O(d(n+r)O(d(n+r)O(d(n+r)O(r)稳定稳定 各种内排序各种内排序方法的性能方法的性能 1、按算法平均时间复杂度分类、按算法平均时间复杂度分类 2、按算法空间复杂度分类、按算法空间复杂度分类 3、按算法稳定性分类、按算法稳定性分类 【例例10- -12】设线性表中每个元素有两个数据项设线性表中每个元素有两个数据项k1和和k2，现对线，现对线 性表按以下规则进行排序：先看数据项性表按以下规则进行排序：先看数据项k1，k1值小的在前，大的在值小的在前，大的在 后；在后；在k1值相同的情况下，再看值相同的情况下，再看k2，k2值，小的在前，大的在后。值，小的在前，大的在后。 满足这种要求的排序方法是满足这种要求的排序方法是。 A.先按先按k1值进行直接插入排序，再按值进行直接插入排序，再按k2值进行简单选择排序值进行简单选择排序 B.先按先按k2值进行直接插入排序，再按值进行直接插入排序，再按k1值进行简单选择排序值进行简单选择排序 C.先按先按k1值进行简单选择排序，再按值进行简单选择排序，再按k2值进行直接插入排序值进行直接插入排序 D.先按先按k2值进行简单选择排序，再按值进行简单选择排序，再按k1值进行直接插入排序值进行直接插入排序 解：解：考虑考虑1：排序数据项顺序：排序数据项顺序：k1、k2还是还是k2、k1 ？ 越重要的数据项越在后面排序越重要的数据项越在后面排序 应为应为k2、k1 标识标识k1k2 18090 27090 38072 47072 k2直接插入排序直接插入排序 标识标识k1k2 38072 47072 18090 27090 标识标识k1k2 27090 47072 18090 38072 k1简单选择排序简单选择排序 相对次序改变相对次序改变 相对次序改变相对次序改变 考虑考虑2：k2选择直接插入排序还是简单选择排序选择直接插入排序还是简单选择排序？ 稳定性稳定性 例如：例如： 答案为答案为D。 标识标识k1k2 18090 27090 38072 47072 k2简单选择排序简单选择排序 标识标识k1k2 47072 38072 18090 27090 标识标识k1k2 47072 27090 38072 18090 k1直接插入排序直接插入排序 相对次序不改变相对次序不改变 相对次序不改变相对次序不改变 因为不同的排序方法适应不同的应用环境和要求，所以选择因为不同的排序方法适应不同的应用环境和要求，所以选择 合适的排序方法应综合考虑下列因素：合适的排序方法应综合考虑下列因素： 待排序的元素数目待排序的元素数目n（问题规模）；（问题规模）； 元素的大小（每个元素的规模）；元素的大小（每个元素的规模）； 关键字的结构及其初始状态；关键字的结构及其初始状态； 对稳定性的要求；对稳定性的要求； 语言工具的条件；语言工具的条件； 排序数据的存储结构；排序数据的存储结构； 时间和辅助空间复杂度。时间和辅助空间复杂度。 4、如何、如何选择合适的排序算法选择合适的排序算法 【例例10- -13】若数据元素序列若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排是采用下列排 序方法之一得到的第二趟排序后的结果，则该排序算法只能序方法之一得到的第二趟排序后的结果，则该排序算法只能 是是。 A. 冒泡排序冒泡排序B. 直接插入排序直接插入排序 C. 选择排序选择排序D. 二路归并排序二路归并排序 说明：本题为说明：本题为2009年全国考研题年全国考研题 【例例10- -14】对一组数据对一组数据(2,12,16,88,5,10)进行排序，若前三趟进行排序，若前三趟 的结果如下：的结果如下： 第第1趟趟：2，12，16，5，10，88 第第2趟趟：2，12，5，10，16，88 第第3趟趟：2，5，10，12，16，88 则采用的排序方法可能是则采用的排序方法可能是。 A. 冒泡排序冒泡排序B. 希尔排序希尔排序 C. 二路归并排序二路归并排序D. 基数排序基数排序 说明：本题为说明：本题为2010年全国考研题年全国考研题 本章完本章完
