对于一个长度为n的无序序列,使用希尔排序进行排序,如果第一趟的增量为d,请问第一趟排序结束时,以下哪个结论是必然成立的?
答案解析
希尔排序第一趟排序是将整个序列分成若干个子序列,每个子序列的元素下标之差为d。对每个子序列进行排序(直接插入排序)。选项A错误,只能保证子序列内的元素有序,不保证任意两个相距d的元素关系,例如,一个子序列为(7,3),另一个子序列(10,2),它们各自有序,但7>2,10>3。选项B错误,仅能保证下标为i mod d = 0的子序列有序,例如增量为4时,可能存在下标为1mod4的子序列比下标为0mod4的子序列大。选项D错误,i/d得到的是商,不是下标的规律。只有选项C的表述最准确,它是将下标为i mod d相同的元素组成子序列进行排序。
正确答案:C