数据结构与算法》课件 第10章 排序.ppt

数据结构课程的内容 第10章 内部排序 第10章 内部排序 10.1 概述 4. 什么叫内部排序？什么叫外部排序？ 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 10.2 插入排序 1) 直接插入排序 例2：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。 直接插入排序的算法分析 2） 折半插入排序 折半插入排序的算法分析 3）希尔（shell）排序（又称缩小增量排序） 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。 时间效率： 希尔排序算法（其中某一趟的排序操作） 附：希尔排序算法分析 课堂练习： 原始序列： 256，301，751，129，937，863，742，694，076，438 原始序列： 256，301，751，129，937，863，742，694，076，438 10.3 交换排序 1) 冒泡排序 冒泡排序的算法分析 2） 快速排序 例1：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。 1.这种不断划分子表的过程，计算机如何自动实现？ 例2：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过程。 整个快速排序的递归算法： 例3：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。 快速排序算法详细分析： 讨论2. “快速排序”是否真的比任何排序算法都快？ 10.4 选择排序 基本思想在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。 简单选择排序 树型选择排序 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素又重建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~ 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 10.4 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫~ 2-路归并排序 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到?n/2?个长度为2或1的有序子序列 再两两合并，……如此重复，直至得到一个长度为n的有序序列为止 当 i 和 j 都在两个表的表长内变化时，根据A[i]与B[j]的关键字的大小，依次把关键字小的对象排放到新表C[k]中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表C[k]中。 10.5 基数排序 多关键字排序 定义： 最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序 按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序 链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法 链式基数排序：用链表作存储结构的基数排序 链式基数排序步骤 设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列 实验 0 1 2 3 4 49 13 65 97 76 7 80 A B 0 1 2 3 4 5 6 7 C i j k 7 13 0 1