内部算法性能分析 第5章 排序算法的改进
对于数组
A[0]，??，a[low],??，a[start-1],a[start],??a[end],??，a[n-1]
0<=low 其中a[0]，??，a[low],??，a[start-1]为已排好序的部分，a[start],??，a[end],??，a[n-1]为待插入的部分，在原来的插入算法中，当我们找到待插入元素a[start]应该插入的位置low后，先将a[start]暂存，然后将a[low],??，a[start-1]后移一位，再将暂存的a[strat]插入a[low]处；在改进的插入算法中，我们还要考察在a[start]之后，是否还存在一个序列a[start+1]，??，a[end],使得 a[start]<=a[start+1]<=??<=a[end]]<=a[low] 如果确实存在这样的的一个序列，则我们可以一次性将a[start],??，a[end]插入a[low]处。在原有的的基础上作一些改进得出如下算法： for(start=1;start { low=0; high=start-1; while(low<=high) { moddle=int((low+high)/2); if(a[moddle]<=a[start]) low=moddle+1; else high=moddle-1; end=start+1; while(end newmove(a,low,start,end); start=end; } } 新的循环移位插入算法如下： L=start-low; p=end-low+1; n=p; m=L; { } for(i=0;i 27 r=p%m; while(r!=0) n=m;m=r;r=n%m; 内部算法性能分析 第5章 排序算法的改进 } outpos=i; inpos=i; temp=a[i+low]; while((outpos=(inpos+L)%p)!=i) { a[inpos+low]=a[outpos+low]; inpos=outpos; } a[inpos+low]=temp; 性能分析：在比较插入过程中，若出现一次可插入的部分有序段a[start],??,a[end],设插入位置在a[low]开始位置处，则涉及移动的序为a[low],??，a[start],??，a[end]，需插入的元素个数为Q=end-start+1,涉及移动的元素总数为P=end-low+1，插入间距为L =start-low；在原插入算法中，每插入一个元素需移动start-low+2次，故总共需移动(start-low+2)(end-start+1)次，而在改进插入算法中，只需移动end-low+m=(end-start+1)+(start-low+m-1)次，其中m=gcd(P,L),两者比值为： 改进插入算法动次数 1 1 原插入算法移动次数 Q P 一般情况下，插入间距L远大于待插入的元素个数Q，所以上式主要取于1/Q，由此可见，只要出现一次有Q个元素的可插入的部分有序段，该部分的插入效率可提高Q倍；整个改进插入算法的效率提高取决于出现可插入的部分有序段的概率和可插入的部分有序段的长度，而且后者比前者更为积极作用。 改过算法的稳定性取决于找到有序的a[start],??，a[end]时的判断条件，如果我们采用 End 作为判断条件，则改进的算法是稳定的；如果为了一次尽可能多的插入元素，提高排序速度采用： End 28 内部算法性能分析 第1章 前 言 第六章 系统实现及数据测试 6.1主界面 当用户启动该程序时进行测试，进入主菜单如图6.1所示： 图6.1主菜单 6.2“排序内部操作过程”菜单 当用户输入“1”时进入“排序内部操作过程”菜单如图6.2所示： 图6.2“排序内部操作过程”菜单 29 内部算法性能分析 参考文献 6.2.1当用户输入0---6的数字时则会随意的进入下一级子菜单 输入“1”进行“直接插入”排序，如图6.3所示： 图6.3“直接插入”排序操作过程 6.2.2输入“2”进行“希尔”排序 如图6.4所示： 图6.4“希尔”排序操作过程 30 内部算法性能分析 参考文献 6.3“性能分析”菜单 当用户输入“2”时进入“性能分析”菜单，如图6.5所示： 图6.5 “性能分析”菜单 6.3.1当用户输入“1”时进行“插入与希尔”排序之间的性能分析比较 如图6.6所示： 图6.6“插入与希尔”排序分析 31