入本元素之左边的有序子表,使其仍然保持有序。()4938659776132749384938()65977613274965493865()6597761327499749386597()761327499749386576977649()1327494938651397769776653813()274949277665973813977665493827()494997139776654938277665494938659776132749()1327384949657697()算法分析:(问题规模为参加排序的元素个数n)比较次数:Tb(n)=n-1移动次数:Tb()=0Tw(n)=∑iTw()=∑(i+1)Ta(n)=(Tb+Tw)/2≈n2/4i=2ni=2n最好情况:正序最差情况:反序算法时间复杂度T(n)=O(n2)810.2.2 其它插入排序⒈折半插入排序算法思想:“定位”除了上述顺序定位法外,还可以利用有序子表特点,采用折半定位法。当定位结束(即L>H)时,aL~ai-1向后移动。L:(a1,a2,a3,…,ak-1,ak,ak+1,…,ai-1)LHai≤<ak≤xLx<akH算法分析:比较次数:Tb(n)=n-1移动次数:不变Tw(n)=∑㏒i≈n㏒ni=1n-1算法时间复杂度T(n)=O(n2)9⒉2路插入排序(将关键字排序在辅助空间中)算法思想:⑴取出表L=(a1,a2,a3,…,ai,…,an)的第1个元素a1存入辅助空间D[1];⑵取出表L的下一个元素ai,如果ai<D[1],则插入到D[1]之左边的有序子表,否则插入到D[1]之右边的有序子表;⑶重复⑵,直到表L的最后一个元素an插入后为止。D[1]D[2]D[n]HT………算法分析:比较次数:不变移动次数:Tb(n)=0Tw(n)=不变Ta(n)=n2/8算法时间复杂度T(n)=O(n2)10
全文预览
