C语言与程序设计ppt-第13章讲义.ppt

华中科技大学计算机学院C语言课程组 C语言与程序设计The C and Programming 本章讲授内容 排序是数据处理领域一种基本且常用的算法。排序的目的之一是便于检索。算法设计的好坏直接影响计算机的运行时间，计算机排序方法较多，时间复杂度差别较大。本章介绍 直接插入排序； shell排序； 归并排序； 算法的时间复杂度； 排序算法的应用实例。 13.1 直接插入排序 直接插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入为止。具体过程为：假设待排序的n个记录存放在数组a中，a被划分成两个子区：有序区(a[0]～a[i-1])和无序区(a[i]～a[n-1])。开始时，i=1，即有序区中只包含1个元素a[0]，无序区中包含有n-1个元素(a[1]～a[n-1])。排序过程中每次从无序区中取出第1个元素a[i]，将它插入到有序区中的适当位置，使a[0]～a[i]成为新的有序区，重复n-1次可完成排序过程。因为这种方法每次使有序区增加1个记录，通常称增量法。 直接插入排序的过程 图13.1给出a={25,10,45,75,15}时的直接插入排序过程，其中大括号内为有序区，后面为无序区。 【例13.1】 编程实现直接插入排序算法 要求计算机生成若干个3位的随机整数，放入数组，完成对数组的升序排序。 分析：本实例要完成两个功能：① 产生随机数放入数组；② 对数组排序。按照结构化程序设计思想，分别定义函数CreateData和InsertSort实现这两个功能,然后编写主函数main对程序功能进行测试，输出排序结果。 函数CreateData 由于需要产生在两个极限值之间取值的数据，为了使函数CreateData有通用性，函数原型为： void CreateData(int a[ ],int n,int low,int high)； 其功能是产生n个low～high之间的随机整数放入数组a中。这样模拟100个考试成绩数据，可以调用CreateData(a，100，0,100)。 产生限定范围随机数的方法 调用rand库函数产生的随机数在0到RAND_MAX之间，需要将其转换到一个更有限的范围，可以运用以下四个步骤： （1）将rand库函数产生的值限制为一个浮点数d，范围是0≤d1。 （2）用乘法将d的值按照需要的范围扩大若干倍； （3）将上述值的小数部分截去，即产生以0为最小值的一定范围的随机整数； （4）修改数值的范围使得从需要的最小值开始。 函数InsertSort InsertSort实现对n个整数的直接插入排序，原型为： void InsertSort(int a[], int n)； 直接插入排序算法步骤： （1）初始时，a[0] 自成1个有序区，无序区为a[1]～a[n-1]，令i=1； （2）将a[i]插入到有序区，过程如下： Ⅰ. 使用变量temp临时保存待插入元素a[i]； Ⅱ. 从有序区尾部开始，查找应插入的位置，若有序区中的元素大于待插入元素，则将其后移一个位置，继续查找，否则，查找过程结束； Ⅲ. 已经腾出的位置即为插入位置，将待插入元素temp直接插入此位置，形成a[0]～a[i]的有序区。 （3）i++，转（2）直到i≥n。 程序 \源程序\ex13_1.c 程序的内循环是实现从后往前查找应插入位置，在查找中，为防止数组越界，要判断j=0。 直接插入排序算法的改进 为了进一步提高直接插入排序的效率，可以引入被称为哨兵的附加元素a[0], 被排序的记录放在 a[1]～a[n-1]中。哨兵a[0]有两个作用：① 暂时存放待插入的元素；② 防止数组下标越界，一旦越界（即j=0），因为和自己比较，循环判定条件不成立使得查找循环结束,不会出现越界（for循环无需判断j=0，提高了效率）。实际上，一切为简化边界条件而引入的附加结点（元素）称为哨兵。引入哨兵后使得测试查找循环条件的时间大约减少了一半，当记录数较大时节约的时间是相当可观的。所以，不能把算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。 通过将折半法应用于查找应插入的位置，可以减少关键字的比较次数，改善算法的性能。 13.2 Shell排序 在直接插入排序算法中，每次插入一个数，使有序序列只增加1个元素，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年实现了这一思想。 希尔排序的基本思想是：先将要排序的n个数按间隔gap（gapn）分成若干组，每组中元素的下标相差gap。对每组中全部元素进行直接插入法排序，然后再用