数据结构(C)严蔚敏——8(精品·公开课件).ppt

第十章 内部排序 学习目标 理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O (n2) 的简单排序方法，O (n·logn) 的高效排序方法和O (d·n)的基数排序方法。 理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 重点和难点 重点：希尔排序、快速排序、堆排序和归并排序等高效方法 难点：希尔排序、快速排序、堆排序和归并排序等高效方法 知识点 排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。 10.1 概述 排序 假设含有n个记录的序列为：{R1，R2，…，Rn}， 它们的关键字相应为{K1，K2，…，Kn}， 对记录序列进行排序就是要确定序号1，2，…，n的一种排列 P1，P2，…，Pn，使其相应的关键字满足如下的非递减（或非递增）的关系： Kp1=Kp2=…=Kpn 使序列成为一个按关键字有序的序列 {Rp1，Rp2，…，Rpn} 目的 利用高效的查找方法，以提高查找效率。 排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存。 外部排序：排序过程中需对外存进行访问的排序。 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序。 交换排序：冒泡排序、快速排序。 选择排序：简单选择排序、堆排序。 归并排序：2-路归并排序。 基数排序 稳定 若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生变化，这种排序称为“稳定”排序；否则是“不稳定”排序。 稳定排序与不稳定排序只是表示所用的排序方法，并不说明哪种方法好与差。 排序基本操作 比较两个关键字大小； 将记录从一个位置移动到另一个位置； 就全面性能而言，很难提出一种被认为最好的方法，每种方法均有优点和适用环境。 本章讨论中，待排记录如下结构。 10.2 插入排序 10.2.1 直接插入排序 基本思想 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 10.2.2 其它插入排序 折半插入排序 基本思想 用折半查找方法确定插入位置的排序。 算法评价 时间复杂度：T(n)=O(n2) 空间复杂度：S(n)=O(1) 2-路插入排序 基本思想 另设一个和L.r同类型的数组d，首先将L.r[1]赋给d[1]，并将d[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d[1]之前或之后的有序序列中。 目的 对折半插入排序的改进，减少记录的移动次数。 10.2.3 希尔(shell)排序 基本思想 是对插入排序的一个改进，也称缩小增量排序。 先将整个待排序记录序列分割成若干个子序列，分别对这些子序列进行直接插入排序；待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 排序过程 取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序； 然后取d2d1，重复上述分组和排序操作； 直至di=1，即所有记录放进一个组中排序为止。 初始关键字：49,38,65,97,76,13,27,49,55,4 一趟希尔排序算法10.4 void ShellInsert ( SqList L，int dk){// 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序// 相比，作了如下修改：1.前后记录位置的增量是dk，不是1；// 2.r[0]只是暂存单元，不是哨兵。当j=0时，插入位置已找到。 for ( i=dk+1; i=L.length; ++i ) if (LT(L.r[i].key , L.r[i-dk].key )) {  // 需将L.r[i]插入有序增量子表 L.r[0] = L.r[i]; for(j=i-dk; j0LT(L.r[0].key,L.r[j].key); j-=dk )　　　　　 L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; 　　　// 插入 } // if } // ShellInsert 希尔排