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

C语言与程序设计

TheCandProgramming

第13章排序

华中科技大学计算机学院

2/5/20231华中科技大学计算机学院C语言课程组本章讲授内容

排序是数据处理领域一种基本且常用的算法。排序的目的之一是便于检索。算法设计的好坏直接影响计算机的运行时间，计算机排序方法较多，时间复杂度差别较大。本章介绍直接插入排序；shell排序；归并排序；算法的时间复杂度；排序算法的应用实例。

2/5/20232华中科技大学计算机学院C语言课程组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个记录，通常称增量法。2/5/20233华中科技大学计算机学院C语言课程组直接插入排序的过程图13.1给出a={25,10,45,75,15}时的直接插入排序过程，其中大括号内为有序区，后面为无序区。第1趟i=1: {25} 10 45 75 15 {10 25} 45 75 15第2趟i=2: {10 25} 45 75 15 {10 25 45} 75 15第3趟i=3: {10 25 45} 75 15 {10 25 45 75} 15第4趟i=4: {10 25 45 75} 15 {10 15 25 45 75}

图13.1直接插入排序的过程2/5/20234华中科技大学计算机学院C语言课程组【例13.1】编程实现直接插入排序算法要求计算机生成若干个3位的随机整数，放入数组，完成对数组的升序排序。分析：本实例要完成两个功能：①产生随机数放入数组；②对数组排序。按照结构化程序设计思想，分别定义函数CreateData和InsertSort实现这两个功能,然后编写主函数main对程序功能进行测试，输出排序结果。2/5/20235华中科技大学计算机学院C语言课程组函数CreateData由于需要产生在两个极限值之间取值的数据，为了使函数CreateData有通用性，函数原型为：

voidCreateData(inta[],intn,intlow,inthigh)；其功能是产生n个low～high之间的随机整数放入数组a中。这样模拟100个考试成绩数据，可以调用CreateData(a，100，0,100)。2/5/20236华中科技大学计算机学院C语言课程组产生限定范围随机数的方法调用rand库函数产生的随机数在0到RAND_MAX之间，需要将其转换到一个更有限的范围，可以运用以下四个步骤：（1）将rand库函数产生的值限制为一个浮点数d，范围是0≤d<1。（2）用乘法将d的值按照需要的范围扩大若干倍；（3）将上述值的小数部分截去，即产生以0为最小值的一定范围的随机整数；（4）修改数值的范围使得从需要的最小值开始。2/5/20237华中科技大学计算机学院C语言课程组函数InsertSortInsertSort实现对n个整数的直接插入排序，原型为：

voidInsertSort(inta[],intn)；直接插入排序算法步骤：（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。2/5/20238华中科技大学计算机学院C语言课程组程序\源程序\ex13_1.c程序的内循环是实现从后往前查找应插入位置，在查找中，为防止数组越界，要判断j>=0。2/5/20239华中科技大学计算机学院C语言课程组直接插入排序算法的改进为了进一步提高直接插入排序的效率，可以引入被称为哨兵的附加元素a[0],被排序的记录放在a[1]～a[n-1]中。哨兵a[0]有两个作用：①暂时存放待插入的元素；②防止数组下标越界，一旦越界（即j=0），因为和自己比较，循环判定条件不成立使得查找循环结束,不会出现越界（for循环无需判断j>=0，提高了效率）。实际上，一切为简化边界条件而引入的附加结点（元素）称为哨兵。引入哨兵后使得测试查找循环条件的时间大约减少了一半，当记录数较大时节约的时间是相当可观的。所以，不能把算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。通过将折半法应用于查找应插入的位置，可以减少关键字的比较次数，改善算法的性能。2/5/202310华中科技大学计算机学院C语言课程组13.2Shell排序在直接插入排序算法中，每次插入一个数，使有序序列只增加1个元素，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年实现了这一思想。希尔排序的基本思想是：先将要排序的n个数按间隔gap（gap<n）分成若干组，每组中元素的下标相差gap。对每组中全部元素进行直接插入法排序，然后再用一个较小的间隔重复上述分组和排序，直至间隔为1，即所有元素放在一组中进行直接插入排序为止。由于每次增量不断缩小，该算法又称为缩小增量排序算法。2/5/202311华中科技大学计算机学院C语言课程组Shell排序的过程间隔的选择是希尔排序的重要部分，只要最终间隔为1，任何间隔序列都可以。Shell本人最初提出取初始gap=n/2，以后每次减小一倍，即gap=gap/2。下图是16个数的Shell排序过程。2/5/202312华中科技大学计算机学院C语言课程组Shell排序算法步骤（1）初始时，间隔gap=n/2，即所有间隔为gap的记录分成一组；（2）从第1组的第2个元素开始，即置循环变量i=gap，顺序扫描整个待排序记录，对每个元素a[i]分别在各组中进行插入排序；Ⅰ.使用变量t临时保存待插入元素a[i]；Ⅱ.在组内从后往前查找应插入的位置。具体方法是，置循环变量j=i-gap，将待插入元素t与a[j]进行比较，若a[j]>t，则将a[j]在组内后移一个位置，然后，j-=gap，继续与组内的前一个元素进行比较；直至a[j]<=a[i]或者数组越界；Ⅲ.将待插入元素t插入相应位置；Ⅳ.i++，转（2）-Ⅰ直到处理完最后一个记录。（3）间隔缩小一半，即gap/=2，转（2），直到比较间隔缩小到0。2/5/202313华中科技大学计算机学院C语言课程组【例13.2】编程实现Shell排序算法要求计算机生成若干个0～100的整数，放入数组，完成对数组的升序排序。分析：定义函数ShellSort实现Shell排序算法,然后编写主函数main进行测试，输出排序结果。\源程序\ex13_2.c函数ShellSort使用了三重for循环，最外层循环用来控制组内元素的间隔gap，从n/2开始，以后减半，直至为1。中间循环用于控制每一个元素，按设置的间距gap，对每一组元素排序。最内层循环使用插入排序法对一组指定间距的元素进行排序。2/5/202314华中科技大学计算机学院C语言课程组13.3归并排序归并（merge）就是将两个或多个有序的数列合成一个有序的数列。若将两个有序的数列合成一个有序的数列则称为二路归并，若将三个有序的数列合成一个有序的数列则称为三路归并，同理，还有四路等多路归并。归并排序是建立在归并操作上的一种有效的排序算法。2/5/202315华中科技大学计算机学院C语言课程组二路归并排序二路归并排序最简单，其基本思想是：将待排序序列a[0]到a[n-1]看成n个长度为1的有序子序列，把这些子序列两两归并，便得到(n/2)个长度为2（最后一个序列的长度可能小于2）的有序子序列，称此为一趟归并排序；然后再把这(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。例如,有7个元素的数组{15，200，105，280，30，9，5}，要进行3趟归并，其排序过程如图13.3所示。2/5/202316华中科技大学计算机学院C语言课程组归并排序的过程例如,有7个元素的数组

{15，200，105，280，30，9，5}，要进行3趟归并，其排序过程如下所示。2/5/202317华中科技大学计算机学院C语言课程组函数merge在归并排序过程中，要反复执行数组中相邻两个有序序列的归并操作。用函数merge实现该归并算法。假设待归并的两个有序序列分别存于数组a中从下标low到下标mid的单元和从下标mid+1到下标high的单元，结果放到数组b中从下标low到下标high的单元。归并过程为：①设定3个索引i=low，j=mid+1，k=low，最初位置分别为3个有序序列的起始位置。②比较a[i]和a[j]的大小，选择相对小的元素复制给b[k]。a[i]<=a[j],则将第1个有序序列中的元素a[i]复制给b[k]，i和k再分别加1，即移动索引到下一位置；否则，将第2个有序序列中的元素a[j]复制给b[k]，j和k再分别加1。③重复步骤②直到索引i或j达到序列尾，即某个有序序列的元素全部比较和复制完。④将另一序列剩下的所有元素直接复制给b。2/5/202318华中科技大学计算机学院C语言课程组函数MergePass在归并算法的基础上，再给出一趟归并排序的算法，用函数MergePass实现,它需要多次调用归并算法。设数组a[0]～a[n-1]中每个有序序列的长度为len（但最后一个序列的长度可能小于len），进行两两归并后的结果放到数组b[0]～b[n-1]中。一趟归并排序的过程为：①设定索引start，指向每一对待合并有序序列的开始位置，初值为0。②对数组a中从索引start开始的两个长度为len的有序序列，调用merge(a,b,start,start+len-1,start+len*2-1)完成归并，然后start加2*len，即移动索引到下一对待合并有序序列的开始位置。③转步骤②直到索引start开始的有序表中有一个的长度小于len④如果还剩下两个不等长的有序序列，则调用merge(a,b,start,start+len-1,n-1)对其完成归并。⑤如果还剩下最后一个有序序列，则把它直接复制到b中即可。2/5/202319华中科技大学计算机学院C语言课程组函数MergeSort归并排序就是反复调用一趟归并排序算法MergePass，第一趟len=1，以后每进行一趟len加倍。设待排序的n个数保存在数组a中，归并过程中使用辅助数组temp，第一趟由a归并到temp，第二趟由temp归并到a，如此反复，直到n个数据成为一个有序序列。在归并过程中，为了将最后的排序结果仍放于a中，需要进行偶数趟，如果实际只需奇数趟，那么最后还要进行一趟，此时temp中只有一个有序序列，它会被直接复制到a中。2/5/202320华中科技大学计算机学院C语言课程组【例13.3】用归并排序法对n个整型数进行升序排序。\源程序\ex13_3.c2/5/202321华中科技大学计算机学院C语言课程组13.4时间复杂度同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。通常用时间复杂度和空间复杂度来衡量算法效率。时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。对于排序问题，如果待处理的数据量巨大，就应该认真分析各种排序法的时间复杂度，从中选出运行效率最高的方法。2/5/202322华中科技大学计算机学院C语言课程组1、时间复杂度的测试【例13.4】按如下步骤编制程序测试算法的时间复杂度：（1）随机产生N个取值在0～20000之间的整数存入数组a；（2）分别采用直接插入排序、Shell排序和归并排序3种算法对数组a作升序排列；（3）对每种算法实现，调用函数ftime记录从算法开始运行到运行结束的时间。试比较三种排序算法的时间复杂度。从测试结果看出，当数据量较小时，3种排序算法相差不大，但是，当数据量增大时，希尔排序和归并排序显示出了明显的优势。因此，当待排序数据n较大时，宜采用Shell、归并排序等时间复杂度小的算法。2/5/202323华中科技大学计算机学院C语言课程组2、时间复杂度的计算虽然一个算法执行所耗费的时间可以上机运行测试得到，但是，评价一个算法的时间性能没有必要都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。算法的实际运行时间因机器而异，它取决于算法中的语句执行次数和每条语句执行的时间，由于每条语句执行的时间取决于计算机，与算法的好坏无关，所以用算法中的语句执行次数来表示算法的时间复杂度。2/5/202324华中科技大学计算机学院C语言课程组渐进时间复杂度如果一个问题的规模是n，解决这一问题的算法中的语句执行次数是n的一个函数，记为T(n)，当n很大时，精确计算T(n)是很难而且也是没有必要的。对于算法时间性能的分析并不需要得到T(n)的精确值，它的变化趋势和规律也能清楚地反映算法的时间消耗。为此，引入渐进时间复杂度，就是时间复杂度的极限情形，用大O表示法O(f(n))表示，O表示数量级，其中，f(n)就是T(n)的最高阶。2/5/202325华中科技大学计算机学院C语言课程组冒泡排序的时间复杂度分析冒泡排序算法的核心代码为：for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(a[j+1]<a[j])swap(a[j],a[j+1]);该段代码的基本操作是比较，因为比较是每次都要做的，而交换不一定每次都要做，T(n)的值就是一共要进行的比较次数（即if语句的执行次数）。最内层循环的次数是(n-i-1)，外层循环i从0到n-2，所以总数是对(n-1-i)求和，其中i从0到n-2，即T(n)=(n-1)+(n-2)+…+1=n(n-1)/2。最高阶是n2冒泡排序算法的时间复杂度是O(n2)，它表明：随着n的增大，算法执行时间的增长率和n2的增长率成正比。2/5/202326华中科技大学计算机学院C语言课程组二分查找的时间复杂度分析二分查找的基本思想和下面代码是一致的：while(n>=1){n/=2;}其时间复杂度就是while循环的次数，令循环次数为k，则有n/2k>=1，即2k<=n，k<=log2n，取最大值k=log2n，二分法的时间复杂度是O(log2n)。2/5/202327华中科技大学计算机学院C语言课程组常见的时间复杂度按数量级递增排列，常见的时间复杂度有：常数阶O(1)、对数阶、线性阶O(n)、线性对数阶、平方阶O(n2)、立方阶O(n3)、…、k次方阶O(nk)、指数阶O(2n)和阶乘阶O(n！)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2/5/202328华中科技大学计算机学院C语言课程组直接插入排序的时间复杂度排序中的两个基本操作是比较和移动，因此排序的时间性能取决于排序过程中这两个操作的次数。对于直接插入排序算法，这两个操作的次数取决于待排数据序列的状态。首先外层循环要进行n-1次插入，每次插入最少比较1次，移动2次（正序）；最多比较i次，移动i+2次（逆序）（i=1，2，…，n-1）。因此，直接插入排序在最好和最坏情况下时间复杂度分别为O(n)和O(n2)。若待排记录序列处于随机状态，则以最坏和最好情况的平均值作为插入排序的时间性能的量度，时间复杂度为O(n2)。直接插入法时间复杂度虽然也为O(n2)，但是它比冒泡排序的性能要好一些。2/5/202329华中科技大学计算机学院C语言课程组shell排序的时间复杂度Shell排序的时间复杂度分析比较复杂，例13.2的算法是三重循环,外循环为log2n数量级,中间循环为n数量级,内循环远远低于n数量级,因为当开始分组较多时，每组的元素少，循环次数就少，后来增量逐渐缩小，分组数也逐渐减少，各组的元素逐渐增多，但由于元素逐渐接近于有序状态，所以循环次数不会随之增加。Shell排序算法的时间复杂度介于和O(n2)，约为O（n1.3）2/5/202330华中科技大学计算机学院C语言课程组归并排序的时间复杂度归并排序要进行(log2n)趟归并，每趟归并的时间复杂度为O(n)。所以，归并排序算法的时间复杂度为O(nlog2n)。但是，归并排序占有附加存储较多，需要另外一个与原排序数组同样大小的辅助数组，其空间复杂度为O(n)，这是该算法的不足。2/5/202331华中科技大学计算机学院C语言课程组【例13.5】试设计一时间复杂度为O(n)的高效排序算法，高考成绩排序。设数组a中存有100万高考学生的数学成绩，且每个分数为0到150之间的整数值。分析：已经介绍的插入、快速、归并等排序算法都是基于比较的，时间复杂度至少为O(nlog2n)，所以前述的各种排序法都满足不了要求。2/5/202332华中科技大学计算机学院C语言课程组计数排序法由于要排序数组元素的值都在0到150的小范围内，因此创建一个长度为151的数组buf，buf中每个元素记录要排序数组中对应分数的出现个数，比如，a中90分有2个，则buf[90]的值为2。假设要排序的数组为a={1,0,3,1,0,1,1}，最大值为3，最小值为0，首先创建一个长度为4的数组buf。然后一趟扫描数组a，得到a中各个元素出现的数目保存到数组buf的对应单元中。一趟扫描完数组a后，buf={2，4，0，1}。从buf的值可知：a中有2个0，3个1，1个3。最后把buf中的记录按每个元素的计数展开到数组a中，排序就完成了。也就是a[0]到a[1]为0，a[2]到a[5]为1……依此类推。\源程序\ex13_5.c2/5/202333华中科技大学计算机学院C语言课程组计数排序法分析计数排序法依靠一个辅助数组来实现，不基于比较，只需要对待排序数组扫描一遍，所以，算法复杂度为O(n)，利用空间换取了时间，就是多占用内存，加快运行速度。这种算法不适合范围很大的数的排序。2/5/202334华中科技大学计算机学院C语言课程组13.5排序程序设计13.5.1多关键字的排序多关键字排序有一定的使用范围，例如，在对高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。2/5/202335华中科技大学计算机学院C语言课程组【例13.6】奥运奖牌的排名编写程序实现奥运会奖牌不同要求的排名：首先按奥运金牌总数排名，当金牌总数相同时，按银牌总数排名，当银牌总数也相同时，按铜牌总数排名，如果三种奖牌数据都相同，按国家名称的字典顺序排序。奥运奖牌的排名为按多关键字的排名。按要求的关键字次序对两个国家的记录进行比较由函数cmp完成，先比较金牌数，金牌不同时函数返回非零值，否则，比较银牌数，银牌不同时函数返回非零值，否则，比较铜牌数，不同时函数返回非零值，最后比较国家名称。2/5/202336华中科技大学计算机学院C语言课程组函数ShellSort排序由函数ShellSort完成，用希尔排序法将指针x指向的n个元素排序，size是各元素的占用空间字节数，fcmp是指向函数的指针，用于确定排序的顺序。因此，该函数对于排序有更好的兼容性，可以对任何数据类型，采取个人需要的排序关键字和排序方法进行升序或降序排序。后面的例13.7也是调用该函数对结构数组排序。使用该函数，要求用户定义一个比较函数，程序中函数cmp是用来比较大小的函数，按要求的关键字顺序比较各种奖牌数，前者多于后者，返回正数，当奖牌数一样时，调用标准库函数strcmp比较国家名称字符串。源程序\ex13_6.c2/5/202337华中科技大学计算机学院C语言课程组13.5.2贪心法很多贪心算法的题目里都要用到排序。贪心法也叫做贪婪法，是求解最优化问题的常用方法之一。它是在求解问题时总作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择，并期望通过每次所做的局部最优选择产生出一个全局最优解。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。贪心是一种解决问题的策略，而不是算法，做出贪心决策的依据称为贪心策略。归纳、分析和选择正确合适的贪心策略，是正确解决贪心问题的关键。如果策略正确，贪心法往往编程简单、运行效率高。2/5/202338华中科技大学计算机学院C语言课程组贪心法求最优装载问题来看一个最优装载问题：给出n个物品及其重量，要求选择尽量多的物品，使总重量不超过C。由于只关心物体的数量，人们会不假思索地选出一个最轻的物品装入；然后从剩下的物品中选出一个最轻的装入；如此一直做下去。每次拿最轻的，就是贪心，它只顾眼前，但却能得到最优解。按照“重量最轻者先装”的贪心策略，只需把所有物品按重量从小到大排序，依次选择每个物品，直至装不下为止。最后编程实现的核心是排序算法。2/5/202339华中科技大学计算机学院C语言课程组【例13.7】给出n（n≤50）个整数，将它们按某种顺序连接成一排，要求最终组成一个最大的多位整数。例如，n=4时，4个整数为7、13、4和246，连接成的最大整数为7424613此题可以用贪心法来求解。容易想到的贪心策略是：高位数字大的整数先取出放前面。对于7、13、4和246四个整数，先取7，再取4，然后246，最后13，连起来就是7424613，肯定是最优解。按此策略，只需将输入的n个整数看作字符串，字符串从大到小排序。但是，当整数相互包含时，如12、121，按照刚才的贪心策略，先121，后12，组成12112，而实际应该组成12121。因此，刚才的贪心策略不对。由于不论怎么连接，最终得到整数的位数总是相同的，所以比较大小的方式，相当于比较连接后的整数对应的字符串的字典序大小。2/5/202340华中科技大学计算机学院C语言课程组正确的贪心策略正确的贪心策略是：先把整数化成字符串，然后再比较a+b和b+a（“+”表示字符串连接），如果(a+b)>(b+a)，就把a排在b的前面，反之则把a排在b的后面。所以，自定义一种字符串的比较规则：即如果(a+b)>(b+a)，则认为a>b。只需要按照这种规则给n个字符串排序即可。这样一来，程序就很简单了，分3步：①把n个整数转化为字符串存入一个字符串数组当中；②按照自定义的规则把n个字符串排序（比较两个字符串大小的函数非常关键）；③输出排序后的数组，这个输出就是答案。源程序\ex13_7.c2/5/202341华中科技大学计算机学院C语言课程组在实际应用中，经常需要永久保存大量数据，这些数据通常以文件的形式存储在硬盘当中。对磁盘文件中数据排序的一般思路是：将数据全部导入内存；用插入、归并和冒泡等排序方法对内存中的数据进行排序；将排好序的数据存入文件。但是，当数据量大到不适合在内存中排序时，就要利用磁盘进行外排序，这就是海量数据的排序问题。13.5.3海量数据的排序2/5/202342华中科技大学计算机学院C语言课程组分段排序假如一个文件中有8亿个整数，整数之间用空格分开，要求对这个文件进行排序。8亿个整数（1个整数为4字节）需要800000000*4=3.2GB内存，一般的设备没有这么多的物理内存，无法将将数据完全导入到内存中。对于海量数据的排序，最常用的解决方案是分段排序，排序过程分以下两阶段：第一阶段：从磁盘中读入M（十万级）条记录到内存，在内存排序，将排好序的数据存入临时文件，重复该过程n次，共生成n个临时文件。第二阶段：使用多路归并将n个临时文件中的数据按序存入输出文件。该分段