希尔排序的执行时间很大程度上依赖于增强的选取。

希尔排序 Description 希尔排序又称“缩小增量排序”，它是一种属于插入排序类的排序方法，但是在时间效率方面较普通的插入排序方法有较大的改进。希尔排序的基本思想是：先将整个待排序的序列分割成为若干子序列，并分别进行直接插入排序，当整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。希尔排序的算法可以描述如下：在本题中，读入一串整数，将其使用以上描述的希尔排序的方法从小到大排序，并输出。Input 输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。 Output 只有1行，包含n个整数，表示从小到大排序完毕的所有整数。请在每个整数后输出一个空格，并请注意行尾输出换行。 Sample Input10 2 8 4 6 1 10 7 3 5 9 Sample Output1 2 3 4 5 6 7 8 9 10

下列排序算法的时间复杂度最小的是____。

A 冒泡排序

B 希尔排序

C 简单选择排序

D 归并排序

当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 ( )【上海交通大学1998一、16(1分)】

此题为判断题(对，错)。

时间复杂度不受数据初始状态影响而恒为的是（ ）。

A.堆排序

B.冒泡排序

C.希尔排序

D.快速排序

在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是()

A.希尔排序

B.堆排序

C.冒泡排序

D.快速排序

由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。( )【电子科技大学2001二、4(1分)】【北京邮电大学2006二、4(1分)】

此题为判断题(对，错)。

A、A．当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快

B、B．当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快

C、C．当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快

D、D．当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢

设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是（）

A.堆排序

B.希尔排序

C.有序链表查找

D.循环链表中寻找最大项

设使用Pratt序列：

对长度为n的任一向量S做希尔排序。

试证明：

a)若S已是(2，3)-有序，则只需o(n)时间即可使之完全有序;

b)对任何，若S已是(2h_k，3h_k)-有序，则只需o(n)时间即可使之h_k-有序;

c)针对序列中的前o(log^tn)项，希尔排序算法需要分别迭代一轮;

d)总体的时间复杂度为o(log²n)。

采用希尔方法排序时,若关键字的排列杂乱无序,则效率最高。()