设数组a中存放了n个数据元素.ppt

9.5 归并排序 归并排序主要是二路归并排序。二路归并排序的基本思想是：设数组a中存放了n个数据元素，初始时我们把它们看成是n个长度为1的有序子数组，然后从第一个子数组开始，把相临的子数组两两合并，得到n/2个（若n/2为小数则上取整）长度为2的新的有序子数组（当n为奇数时最后一个新的有序子数组的长度为1）；对这些新的有序子数组再两两归并；如此重复，直到得到一个长度为n的有序数组为止。多于二路的归并排序方法和二路归并排序方法类同。 二路归并排序算法各次归并排序过程 9.6 基数排序 基数排序算法的基本思想是：设待排序的数据元素是m位d进制整数（不足m位的在高位补0），设置d个桶，令其编号分别为0,1,2,…,d-1。首先按最低位（即个位）的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；再对一次基数排序得到的数据元素序列按次低位（即十位）的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。 基数排序算法的排序过程 链式队列的基数排序算法存储结构 9.7 各种排序算法的性能比较 排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性 直接插入排序 O(n) O(n2) O(n2) O(1) 稳定 希尔排序 O(n1.3) O(1) 不稳定 直接选择排序 O(n2) O(n2) O(n2) O(1) 稳定 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n) 不稳定 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 基数排序 O(mn) O(mn) O(mn) O(n) 稳定 第9章 排序 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 归并排序 9.5 基数排序 9.6 各种排序算法的性能比较 本章主要知识点： 排序的基本概念和衡量排序算法优劣的标准，其中衡量标准有算法的时间复杂度、空间复杂度和稳定性 直接插入排序，希尔排序 直接选择排序，堆排序 冒泡排序，快速排序 归并排序 基数排序 各种排序算法的性能比较 9.1 排序的基本概念 排序是对数据元素序列建立某种有序排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。 关键字分主关键字和次关键字两种。对要排序的数据元素集合来说，如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字。 不满足主关键字定义的关键字称为次关键字。 学生成绩表 排序分内部排序和外部排序两种。内部排序是把待排数据元素全部调入内存中进行的排序。如果数据元素的数量太大，需要分批导入内存，分批导入内存的数据元素排好序后再分批导出到磁盘和磁带外存介质上的排序方法称作外部排序。 排序算法的比较标准： 1. 空间复杂度 2. 时间复杂度 3. 稳定性 9.2 插入排序 9.2.1 直插入排序 直接插入排序的基本思想是：顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大。当子集合大小最终和集合大小相同时排序完毕。 直接插入排序过程 9.2.2 希尔排序 希尔排序的基本思想是：把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称作缩小增量排序。 一个希尔排序的排序过程 9.3