插入排序基本思想.doc

,插入排序基本思想 插入排序的基本思想：每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的子文件的适当位置，直到全部的记录插入完成为止。 本节介绍二种插入排序方法：直接插入排序和希尔排序。 先介绍简单的一种插入排序方法：直接插入排序直接插入排序基本思想： 直接插入排序 1、基本思想： 假设待排序的记录存放在R1.n数组中，初始时该数组R1自成有序区。无序区为R2.n，从R2.n中的R2开始到Rn，依次将Ri插入到有序区中，生成最终的有序区。 2、直接插入排序： 通常将一个记录Ri 插入到当前有序区，使得插入后的仍保证区间里面的记录是有序的，该操作称为第i-1趟插入排序。 排序过程的某一个中间时刻，R被划分为二个子区，有序区和无序区，R1.i-1是已排好的有序区间，Ri.n为无序区。 直接插入排序的基本操作是将当前无序区的第一个记录Ri 插入到有序区中适当的位置上，使得R1.i变为新的有序区。因为这种方法每次是的有序区增加一个记录，因此通常称为增量法。 一趟直接插入排序方法 1、简单方法 首先在当前有序区中查找R1.i-1中Ri应该插入的正确位置;然后将Rk.i-1的记录均向后移动一个位置，腾出K位置上的空间插入Ri。如果Ri的关键字大于等于R1.i-1中的记录，那么Ri插入到原位置。即i位置。 2、改进的方法 一种查找比较操作和记录移动操作交替进行的方法。 具体的做法： 将待插入的Ri关键字从右向左依次与有序区中记录Rj关键字进行比较(1<j<i-1): 1、若Rj的关键字大于Ri的关键字则将Rj后移一个位置。 2、若Rj的关键字小于或者等于Ri的关键字，则查找过程结束，j+1即为Ri的插入位置。 关键字比Ri的关键字打的记录均已经后移，所以j+1的位置已经腾空，只要将Ri插入到该位置即可完成一趟直接插入排序。直接插入排序算法源码 1 void lnsertSort(int R) 2 /对顺序表R中的记录R1.n按递增序进行插入排序 3 int i，j； 4 for(i=2;i<=n；i+) /依次插入R2，Rn 5 if(Ri.key<Ri-1.key)/若Ri.key大于等于有序区中所有的keys，则Ri 6 /应在原有位置上 7 R0=Ri;j=i-1; /R0是哨兵，且是Ri的副本 8 do 9 /从右向左在有序区R1i-1中查找Ri的插入位置10 Rj+1=Rj； /将关键字大于Ri.key的记录后移11 j- ；12 13 while(R0.key<Rj.key)； /当Ri.keyRj.key时终止14 Rj+1=R0； /Ri插入到正确的位置上15 /endif16 /该排序算法中加入了附加记录R0,其作用是：1、进入查找插入位置循环之前，他保存了Ri的副本。使得不因为记录后移而丢失Ri的内容。2、他的主要作用是：在查找循环中监视下标变量j是否越界，一旦越界即j=0，则因为R0.key于自己比较发现值不小于自己，致使循环条件不满足，则终止循环，从而避免了该循环体中每次都要检测j是否越界。注意：一切为了简化边界条件而引入的附加结点元素都可以称为哨兵。【例】单链表中的头结点实际上是一个哨兵引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。算法分析1算法的时间性能分析 对于具有n个记录的文件，要进行n-1趟排序。 各种状态下的时间复杂度： 初始文件状态 正序 反序 无序(平均) 第i趟的关键 1 i+1 （i-2）/2 字比较次数 总关键字比较次数 n-1 (n+2)(n-1)/2 n2/4 第i趟记录移动次数 0 i+2 （i-2）/2 总的记录移动次数 0 (n-1)(n+4)/2 n2/4 时间复杂度 0（n） O（n2） O（n2） 2算法的空间复杂度分析 算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。3直接插入排序的稳定性 直接插入排序是稳定的排序方法。希尔排序希尔排序(Shell Sort)是插入排序的一种。希尔排序基本思想 基本思想： 对于一个无序集合R1.n，从其中去一个小于n的整数r作为第一个增量，把文件的全部记录分成r个组，所有距离为r的倍数的记录放在一个组中，然后对每个分组进行直接插入排序，然后去第二个增量，r1<r重复上述的分组与排序，知道所取得增量rn=1,即所有的记录放在同一个分组中进行直接插入排序为止。 该方法实质上是一个分组插入方法。 分组的计算公式如下： int groupNum = n / 2; n代表元素的个数Shell排序的算法实现1 不设监视哨的算法描述 1 void ShellPass(SeqList R，int d) 2 2 /希尔排序中的一趟排序，d为当前增量 3 3 for(i=d+1;i<=n；i+) /将Rd+1n分别插入各组当前的有序区 4 4 if(Ri.key<Ri-d.key) 5 5 R0=Ri;j=i-d； /R0只是暂存单元，不是哨兵 6 6 do /查找Ri的插入位置 7 7 Rj+d；=Rj； /后移记录 8 8 j=j-d； /查找前一记录 9 9 while(j>0&&R0.key<Rj.key)；10 10 Rj+d=R0； /插入Ri到正确的位置上11 11 /endif12 12 /ShellPass13 13 14 14 void ShellSort(SeqList R)15 15 16 16 int increment=n； /增量初值，不妨设n>017 17 do 18 18 increment=increment/3+1； /求下一增量19 19 ShellPass(R，increment)； /一趟增量为increment的Shell插入排序20 20 while(increment>1)21 21 /ShellSort22 22注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。算法分析1增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： 最后一个增量必须为1； 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。2Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因：当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。3稳定性 希尔排序是不稳定的。