【数据结构与算法】排序

1、第十章 内部排序,10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.3 shell排序 10.3 交换排序（快速排序） 10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的比较讨论,10.1 内部排序概述,排序(Sorting): 将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。 排序方法的稳定性： 对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的。反之，称该排序方法是不稳定的。 内部排序 待排序记录存放在计算机的内存中进行排序。 外部排

2、序 待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。,排序的分类,按排序过程依据的不同原则进行分类： 插入排序、 交换排序、 选择排序、 归并排序和 基数排序 按工作量分类，可以分为三类： (1)简单的排序方法,其时间复杂度为O(n2); (2)先进的排序方法,其时间复杂度为O(nlog2n); (3)基数排序，其时间复杂度为O(dn);,排序的基本操作和记录的存储方式,排序过程中需要的两种基本操作： （1）比较关键字的大小； （2）将记录从一个位置移至另一个位置。 待排序记录序列可有下列三种存储方式： （1）记录存放在一组连续的存储单元中；类似于线性

3、表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。 （2）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。- 链排序 （3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。- 地址排序,待排序记录的数据类型,#define MAXSIZE 20 typedef int KeyType; typedef struct KeyType key; InfoType otherinfo; RcdType; typedef struct

4、RedType rMAXSIZE+1; int length; SqList;,10.2 插入排序10.2.1 直接插入排序,例：序列为49，38，65，97，76，13，27，49 (49)，38，65，97，76，13，27，49 (38) (38，49)，65，97，76，13，27，49 (65) (38，49，65)，97，76，13，27，49 (97) (38，49，65，97)，76，13，27，49 (76) (38，49，65，76，97)，13，27，49 (13) (13，38，49，65，76，97)，27，49 (27) (13，27，38，49，65，76，97)

5、，49 (49) (13，27，38，49，49，65，76，97),直接插入排序算法,void InsertSort(SqList / InsertSort,时间：最坏情形判断与移动各接近 n(n+1)/2; 最好情形判断n次，无移动；故时间复杂度：O(n2) 空间：一个辅助空间,10.2.2 Shell排序算法,基本思想： 先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。 算法复杂度：O(n3/2),Shell排序举例（非稳定的）,10.3 交换排序 1. 冒泡排序（其时间复杂度O(n2)）,初 始 关 键 字,第 一

6、 趟 排 序 后,第 二 趟 排 序 后,第 三 趟 排 序 后,第 四 趟 排 序 后,第 五 趟 排 序 后,第 六 趟 排 序 后,2. 快速排序- 对冒泡排序的一种改进,基本思想： 通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。,快速排序举例,初始关键字：49，38，65，97，76，13，27，49,一趟完成后：27，38，13，49，76，97，65，49,快速排序分析,快速排序的平均时间为T(n) = knlog(n) k为某个常数因子 经验表明,在同数量级的排序方法中,快速排序的

7、常数因子k最小. 就平均时间而言,快速排序是最好的. 若初始序列按关键字基本有序,快速排序蜕化为起泡排序,其时间复杂度为O(n2)。 改进的方法，用“三者取中”的法则选取枢轴记录（pivotkey).,快速排序举例,初始关键字：49，38，65，97，76，13，27，49,一趟完成后：27，38，13，49，76，97，65，49,快速排序算法（一）,int Partition(SqList ,快速排序算法（二）,void Qsort(SqList / QuickSort,10.4 选择排序 10.4.1. 简单选择排序（其时间复杂度O(n2)）,基本思想： 每一趟在序列的后n-i+1(i=

8、1,2,.,n-1)个记录中选取关键字最小的记录作为第i个记录。,void SelectSort(SqList / 与第i个记录交换 / SelectSort,初始关键字：49，38，65，97，76，13，27，49 第一次交换：13，38，65，97，76，49，27，49,10.4.3 堆排序,堆的定义： n个元素的序列k1,k2,.,kn当且仅当满足下列条件时，称之为堆。,堆举例： 96,83,27,38,11,09) 12,36,24,85,47,30,53,91,完全二叉树,且所有非叶 结点的值均不大于(不小 于)其左、右孩子结点的值,实现堆要解决的问题,（1）如何从一个无序序列建

9、成一个堆？ （2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？,无序序列建成一个堆（从第n/2到1个元素） 49，38，65，97，76，13，27，49,10.5 归并排序(Merging Sort),将两个或两个以上的有序表组合成一个新的有序表 2-路归并举例:,初始关键字: 49 38 65 97 76 13 27,一趟归并后: 38 49 65 97 13 76 27,二趟归并后: 38 49 65 97 13 27 76,三趟归并后: 13 27 38 49 65 76 97,2-路归并算法,void Merge(RcdType SR, RcdType /复制剩余的SRj.n

10、 / Merge,归并算法的特点,需要辅助空间: O(n) 整个归并需要 log2n 趟 时间复杂度: O(n log2n) 它是稳定的排序方法 思想可以推广到 “多-路归并“,10.6 基数排序(Radix Sorting),不需要进行关键字之间的比较 借助多关键字排序的思想对单关键字排序 10.6.1 多关键字排序 2345678910JQKA 2345678910JQKA 2345678910JQKA 2345678910JQKA 花色 ()优先于面值(23.A) 最高位优先(MSD): 分成子序列分别排序 最高位优先(LSD): 通过若干次“分配”和“收集“,10.6.2 基数排序,借

11、助“分配”和“收集“两种操作对单关键字进行排序。例如: 278-109-063-930-589-184-505-269-008-083,278,109,063,930,184,505,589,269,008,083,930-063-083-184-505-278-008-109-589-269,930-063-083-184-505-278-008-109-589-269,278,109,063,930,184,505,589,269,008,184,505-008-109-930-063-269-278-083-184-589,505,008,109,930,063,269,278,083,

12、083,589,008-063-083-109-184-269-278-505-589-930,基数排序分析(d个关键字的取值范围rd）,“收集”重复的次数为d; 一轮“分配”的次数为n+rd; 时间复杂度为O(d(n+rd); 链式基数排序所需辅助存储量为O(n)。,10.7 各种排序方法的比较讨论,排序方法 简单排序 Shell排序 快速排序 堆排序 归并排序 基数排序,平均时间 O(n2) O(n3/2) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd),最坏情况 O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(d(n+rd),辅助存储 O(1) O(1) O(logn) O(1) O(n) O(rd),插入, 交换, 选择, 归并, 基数排序,几个结论,(1)平均时间性能快速排序最佳,但最坏情况下的时间性能不如堆排序和归并排序. (2)简单排序以“直接插入排序”最简单,当序列“基本有序”或n较