数据结构讲义第10章.教学提纲.ppt

《数据结构讲义第10章.教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构讲义第10章.基本概念2、排序的稳定性：假设Ki=Kj,i≠j，且在排序前的序列中Ri领先Rj（即i＜j），若在排序后的序列中，Ri仍领先Rj，则称所用的排序方法是稳定的。若在排序后的序列中，Rj领先Ri，则称所用的排序方法是不稳定的。排序算法的稳定性是指对所有输入实例而言，只要能找出一个实例能证明其是不稳定的，就能说明它是不稳定的。3、内排序：排序期间，全部记录都存放在内存。外排序：排序期间，只有部分记录在内存，随时存在记录的内外存交换。基本概念4、排序过程进行的操作：①比较操作：比较两个关键字的大小--必不可少的操作。

2、②改变记录的逻辑联系或将一个记录从一个位置移动到另一个位置。是否需要移动，与待排序记录的存储方式有关：①以顺序表作为存储结构：当两个记录关键字不满足给定关系时，必须移动记录。②以链表作为存储结构，通过修改指针来改变记录的逻辑关系，不需移动记录。通常这种排序为链表排序。③若存储在一组地址连续的存储单元中，另设一地址向量来指示各记录的存储位置。排序过程中通过移动地址向量中的记录的“地址”来改变记录的次序关系。（排序完成后再调整记录的存储位置，这种存储方式的排序称为地址排序。）基本概念5、评价排序算法的标准：①执行时间；②所需辅助空间。

3、若所需辅助空间不依赖于问题的规模n，即辅助空间为O(1)，则称为就地排序。非就地排序所要求的辅助空间为O(n)。排序算法的时间开销主要是关键字的比较次数和记录的移动次数。算法执行时间不仅取决于问题的规模，而且取决于输入实例中的数据状态，分析中一般给出最好、最坏和平均的三种时间性能评价。本章所讨论的排序，除基数排序外，都是采用顺序表作为存储结构。基本概念为了讨论方便，假设记录关键字均为整数。待排序的记录的数据类型为：#definen100typedefintKeyType;typedefstruct{KeyTypekey;InfoT

4、ypeotherinfo;}RecType;typedefRecTypeSeqList[n+1];若关键字类型没有比较算符，可事先定义宏或函数来表示比较算符。如字符串比较。§10.2插入排序一、插入排序算法的基本思想：先将第一个记录看作一个有序子表，然后依次从第二个记录开始逐个将记录插入到前面的有序子表中。二、直接插入排序----线性插入排序假设：待排序记录放在数组R[1..n]中。把数组中记录分成两个区R[1..i-1]和R[i..n]，其中R[1..i-1]为有序区，R[i..n]为无序区。然后把无序区中记录依次插入到有序区中

5、形成新的有序区。这种方法通常称为增量法，因为每次在有序区中增加一个新记录。初始时，1个记录自然有序，然后从i=2开始，直到i=n为止，依次将R[i]插入到有序区中。直接插入排序寻找R[i]的插入位置的方法：从j=i-1的记录位置开始依次向前比较:若R[i].key

6、。在查找插入位置的过程中，为了避免测试j>=1，在R[0]处设置监视哨。即令：R[0]=R[i]这样，在向前搜索过程中，总有一个记录有R[i].key≥R[j].key。因此，引入哨兵元素简化了边界条件的判断，使得测试查找循环条件的时间减少一半。直接插入排序设有一组待排序记录的关键自为：{49，38，65，97，76，13，27，49}【初始关键字序列为】（49），38，65，97，76，13，27，49i=2（38）（38，49），65，97，76，13，27，49i=3（65）（38，49，65），97，76，13，27，49

7、i=4（97）（38，49，65，97），76，13，27，49i=5（76）（38，49，65，76，97），13，27，49i=6(13)（13，38，49，65，76，97），27，49i=7(27)（13，27，38，49，65，76，97），49i=8(49)（13，27，38，49，49，65，76，97）监视哨直接插入排序算法：voidInsertSort(SeqLiat&L){inti,j;for(i=2;i<=L.length;++i)//对每一个Ri∈RifLT(L.r[i].key,L.r[i-1].key)

8、{L.r[0]=L.r[i];for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)//寻找插入位置jL.r[j+1]=L.r[j];//将j..i-1的记录后移一格L.r[j+1]=L.r[0];//将Ri插入到位值j}