对初始数据序列(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 )进行希尔排序。若第一趟排序结果为(1,3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ),第二趟排序结果为(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ),则两趟排序采用的增量(间隔)依次是 。
A. 3, 1
B. 3,2
C. 5,2
D. 5,3
第一趟排序,只需看1,8。其中1移动到了8的位置,说明增量不可能是3。根据选项排除AB 第二趟排序,只需看2,3。这两个调换了位置,增量为3
D
先看第一趟,1从最开始的...
用户登录可进行刷题及查看答案
先看第一趟,1从最开始的5号位移动到0号位,说明第一趟步长是5,直接排除A,B;再看第二趟,2从第一趟排序结果的第4位移动到1号位,说明第二趟步长是3
void shellsort(int[] arr, int length) { int index = 0; int value = 0; for(int flag = length/2; flag>0; flag /= 2;) { for(int i=flag; i<length; i++) { index = i; value = arr[index]; if(value < arr[index-flag]) { while((index-flag > 0 ||index-flag == 0) && value < arr[index-flag]) { arr[index] = arr[index-flag]; index = index - flag; } arr[index] = value; } } } }
这道题考察希尔排序的特征,希尔排序中间过程是间隔有序的。
需要考察的间隔很多,我们可以直接参考选项,第一趟排序的间隔只有3和5,我们先考察3,从数组第一个元素开始为1, 5, 4, ...到这里就没必要查下去了,数组已经不单调了。直接排除A和B。
下面考察C和D,只需要观察第二题排序的间隔。我们先考察2,从数组第一个元素开始为1, 6, 3, ...到这里就没必要查下去了,数组已经不单调了。直接排除C。
现在A、B和C都被排除,只能选D,当然不放心的话你也可以验证一下D,完全符合希尔排序的特征。
登录后提交答案