数据结构 第2版 宗大华 陈吉人 数据结构 课件-9

《数据结构 第2版 宗大华 陈吉人 数据结构 课件-9》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序的基本概念；第9章排序1.2.3.本章讲述内容：4.基本的插入排序(直接插入排序、折半插入排序、表插入排序)算法；基本的交换排序(冒泡排序、快速排序)算法；基本的选择排序(直接选择排序、堆排序)算法。9.1排序的基本概念给定一组记录：r1、r2、…、rn，对应的关键字为：k1、k2、…、kn。将这些记录重新排列成：rs1、rs2、…、rsn，使得对应的关键字满足：ks1≤ks2≤…≤ksn的升序条件。这种重排一组记录、使其关键字值具有非递减顺序的过程，就称为“排序”。让关键字排序后表现出一种非递增关系也是可以的，也是排序。作为排序依据的关键字，可以是记录的主关键字，也可

2、以是记录的次关键字。由于主关键字可以唯一确定一条记录，因此用它来进行排序时，排序的结果是唯一的。使用次关键字进行排序时，排序的结果可能不唯一。本章所有的排序算法都适用于处理具有相同关键字值的排序问题。假定待排序的记录中有相同关键字值的记录。若经过某种排序后，那些有相同关键字值的记录间的相对位置仍然保持不变，那么就称这种排序方法是“稳定的”，否则就是“不稳定的”。所谓“内排序”，指待排记录序列全部存放在内存，整个排序过程都在内存里完成；所谓“外排序”，指内存中容纳不下所有待排记录序列，排序过程中需要不断地与外存进行数据交换。本章介绍的只是有关内排序的算法。衡量排序算法性能好坏

3、的标准，除了运行时间外，通常是看关键字的比较次数和记录的移动次数，分为最好情况(常发生在数据已经有序时)、最坏情况(常发生在数据按反序存放时)和平均情况(常是数据随机存放时)三种。......已知待排序记录的关键字为：77，44，99，66，33，55，88，22利用直接插入排序完成对它们的排序，给出最终的排序结果。9.2插入排序9.2.1直接插入排序例：插入排序的含义是：一趟一个地将待排记录按照关键字大小，插入到前面已经排好序的部分记录的适当位置中，使其成为一个新的有序序列，直到所有待排记录全部插入完毕。.直接插入排序的基本思想是：初始认可第1个记录已排好序，然后用第2个

4、记录与它进行比较，插入到它的相应位置；再用第3个记录与已排好序的两个记录的子序列比较，插入到它的相应位置。这样，总是用第i个记录与前面排好序的i−1个记录的子序列比较，插入到它的相应位置。这一过程一直进行到最后一个记录时结束。.A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]初始状态：[77]44996633558822第1次扫描：[4477]第2次扫描：[447799]第3次扫描：[44667799]第4次扫描：[3344667799]第5次扫描：[334455667799]第6次扫描：[33445566778899]第7次扫描：[223344556677

5、8899]最终结果：2233445566778899把所有待排记录存放在一个一维数组A里，如图所示。解：然后做7次扫描，进行直接插入排序，得到最终结果。Ins_Sort(Ar,n){for(i=2;i<=n;i++){temp=Ar[i];j=i-1;while((temp.key=1)){Ar[j+1]=Ar[j];j--;}Ar[j+1]=temp;}}算法由for里套一个while组成，for的作用是逐一考察记录Ar[2]～Ar[n]，以确定它们在已排序序列里的正确位置。因此，该循环总共要执行n−1次。while控制每次已排好序的比较范

6、围，每个被考察的关键字总是在这个范围内进行比较，找出它的插入位置，并完成插入。.直接插入排序算法算法9-1算法描述(1)算法分析(2)实施直接插入排序时，一维数组元素的存储结构如图所示。.keydata排序依据的记录关键字记录的其他数据项.每次进入while之前，被考察关键字Ar[i]都放在临时工作单元temp里，比较范围是已经排好序的数组Ar[1]～A[i-1]。.temp.key与比较范围内关键字的比较是从后往前进行的，即先与Ar[i-1].key比较，再与Ar[i-2].key比较，如此等等。若被考察记录的关键字小于比较范围内的关键字(即temp.key

7、key)，那就把该记录往后移动一个位置(Ar[j+1]=Ar[j])，以便最终能得到一个空位子，它就是被考察记录应该插入的地方。在排序时，key是最重要的数据域。若待排记录序列初始时就是关键字有序的，那么这是最好的情形。for循环做一次，进行一次关键字比较就能够得到插入位置，所以总共需要做n−1次关键字比较，没有任何记录的移动。算法讨论(3)..若待排记录序列初始时是关键字反序的，那是最坏的情形。做一次while，就要与前面已排序子序列进行i−1次比较(2≤i≤n)。所以：while循环做一次，就要移动i−1个记录