初始状态,setp=49167356229124657 第一趟结果,step=22967355791 第二趟结果,step=1295735624679172 第三趟结果 2935465762677291 图7-2希尔排序算法的执行过程
初始状态，setp=4 91 67 35 62 29 72 46 57 第二趟结果，step=1 29 57 35 62 46 67 91 72 第三趟结果 29 35 46 57 62 67 72 91 第一趟结果,step=2 29 67 35 57 91 72 46 62 图 7-2 希尔排序算法的执行过程
2希尔排序的算法 void shell_sort(int r[N+dIl, int d(tD) i int I, j, k, h; rectype temp for(i=0; i<d[O]; i++) Ri]. key =-maxint h=dk;/*取本趟增量* for(i=h+d1;i<n+dl;i++)//按增量分组将数据插入有序区 i temp=R[i;j=i-h while(temp. key <RG. key)( Ri+]=Rel;j=j-h;) RU+h=temp; K++ 3 while(h!=1)
2.希尔排序的算法 void shell_sort(int R[N+d1],int d[t]) { int I,j,k,h; rectype temp; for(i=0; i<d[0];i++) R[i].key = - maxint; k = 0; do { h=d[k]; /*取本趟增量*/ for ( i=h+d1; i<n+d1; i++) //按增量分组将数据插入有序区 { temp=R[i]; j = i-h; while ( temp.key < R[j].key) { R[j+h] = R[j]; j = j –h; } R[j+h] = temp; } K++； } while ( h!=1); }
3.希尔排序的效率分析 ●虽然我们给出的算法是三层循环,最外层循环为 logn数量级,中间的for循环是n数量级的,内循环远 远低于n数量级,因为当分组较多时,组内元素较少 ,此循环次数少;当分组较少时,组内元素增多, 但已接近有序,循环次数并不增加。因此,希尔排 序的时间复杂性在O( nlog,n)和O(n2)之间,大致 为O(n13)。 由于希尔排序对每个子序列单独比较,在比较时进 行元素移动,有可能改变相同排序码元素的原始顺 序,因此希尔排序是不稳定的。 如:4,9,7,6,5,4,1
3．希尔排序的效率分析 虽然我们给出的算法是三层循环，最外层循环为 log2n数量级，中间的for循环是n数量级的，内循环远 远低于n数量级，因为当分组较多时，组内元素较少 ，此循环次数少；当分组较少时，组内元素增多， 但已接近有序，循环次数并不增加。因此，希尔排 序的时间复杂性在O（nlog2n）和O（n 2 ）之间，大致 为O（n 1.3）。 由于希尔排序对每个子序列单独比较，在比较时进 行元素移动，有可能改变相同排序码元素的原始顺 序，因此希尔排序是不稳定的。 如：4，9，7，6，5，4，1