[计算机软件及应用]数据结构

《[计算机软件及应用]数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概述插入排序快速排序选择排序归并排序小结第十章内部排序概述排序：将一组杂乱无章的记录按一定的规律顺次排列起来。关键字(key):通常数据记录有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分记录，作为排序依据。该域即为关键字。主关键字:如果在待排序记录序列中各个记录的关键字互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯一的。次关键字:待排序记录序列中有些记录的关键字可能相同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯一。排序算法的稳定性:如果在记录序列中有两个记录R[i]和R[j]，它们的关键字k[i]==k[j]

2、，且在排序之前，记录R[i]排在R[j]前面。如果在排序之后，记录R[i]仍在记录R[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据记录全部存放在内存的排序；外排序是指在排序期间全部记录个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的记录比较次数与记录移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受记录关键字序列初始排列及记录个数影响较大的，需要

3、按最好情况和最坏情况进行估算。算法执行时所需的附加存储:评价算法好坏的另一标准。待排序记录的存储方式：以一维数组作为存储结构，排序时必须实际移动记录；以链表(动态链表或静态链表)作为存储结构，排序时不用物理移动记录，只需修改指针；有的排序方法难于在链表上实现，且需要避免排序过程中的记录移动，可将待排序记录本身存储在一组地址连续的存储单元内，同时附设一个指示记录存储位置的地址向量，排序过程中不移动记录，而移动地址向量中这些记录的地址。待排序记录的数据类型说明：#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypek

4、ey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE];intlength;}SqList;插入排序(InsertSorting)直接插入排序的基本思想是：当插入第i(i1)个记录时，前面的R[1],R[2],…,R[i-1]已经排好序。这时，用R[i]的关键字与R[i-1],R[i-2],…的关键字顺序进行比较，找到插入位置即将R[i]插入，原来位置上的记录向后顺移。基本方法：每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。直接插入排序(I

5、nsertSort)各趟排序结果21254925*1608123456123456temp21254925*160825i=2123456temp21254925*160849i=321254925*1608123456tempi=425*123456temp21254925*1608i=516123456temp21254925*1608i=60821254925*1608123456i=5时的排序过程完成1616123456temp21254925*0816i=5j=44916123456temp21254925*0816i=5j=325*1621254925*0

6、812345616i=5j=22516123456temp214925*081625i=5j=1123456temp21254925*081621i=5j=016对顺序表直接插入排序的算法：voidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;++i)if(L.r[i].key

7、;//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}保存记录L.r[i]的副本；监视下标j是否越界，自动控制循环结束说明：监视哨L.r[0]的作用：直接插入排序的算法简洁，容易实现。从时间来看，排序的基本操作为：比较两个记录的大小和移动记录。其中：最小比较次数：Cmin=n-1=O(n)最大比较次数：Cmax=(2+3+…+n)=(n+2)(n-1)/2=O(n2)最小移动次数：Mmin=0最大移动次数：Mmax=(2+1+3+1+…+n+1)=O(n2)若待排序记录序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情