在下列排序算法中，在待排序序列为有序的情况下，（）的时间复杂度是O（)，其中n为待排序序列的数据元素个数。

在下列排序算法中，在待排序序列为有序的情况下，（ ）的时间复杂度是O()，其中n为待排序序列的数据元素个数。

A、简单插入排序

B、堆排序

C、快速排序

D、归并排序

在原始序列已经有序(升序或降序)的情况下，(44)算法的时间复杂度为O(n2)。

A．堆排序

B．插入排序

C．快速排序

D．归并排序

不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是__________，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__________。 【中国人民大学2001一、3(2分)】

下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(23)。 void select_sort(int a[], int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0；i

A．O(n3)

B．O(n2)

C．O(n)

D．O(n4)

下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[]，int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0；i＜n-1；++i){ j=i； for(k=i+1；k＜n；++k)if(a[k]＜a[j])j=k； if(j!=i){w=a[j]；a[j]；a[i]；a[i]=w} )//select_sort

A．O(n2)

B．O(n3)

C．O(n4)

D．O(n)

● 以下关于快速排序算法的描述中，错误的是 （64） 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为 （65） 时，排序效率最高（令序列的第一个元素为基准元素）。

（64）

A. 快速排序算法是不稳定的排序算法

B. 快速排序算法在最坏情况下的时间复杂度为O(nlgn)

C. 快速排序算法是一种分治算法

D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

（65）

A. 45,12,30,25,67,52,85

B. 85,67,52,45,30,25,12

C. 12,25,30,45,52,67,85

D. 45,12,25,30,85,67,52

● 以下关于快速排序算法的描述中，错误的是 （64） 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为 （65） 时，排序效率最高（令序列的第一个元素为基准元素）。

（64）

A. 快速排序算法是不稳定的排序算法

B. 快速排序算法在最坏情况下的时间复杂度为O(nlgn)

C. 快速排序算法是一种分治算法

D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

（65）

A. 45,12,30,25,67,52,85

B. 85,67,52,45,30,25,12

C. 12,25,30,45,52,67,85

D. 45,12,25,30,85,67,52

●下面算法是实现对n个整数的序列进行选择排序，其中序列的"长度"n为问题的规模。该算法的时间复杂度为 (23) 。

void select_sort(int a[]，int n)

{

//将a中整数序列重新排列成从小到大有序的整数序列

for(i=0；i<n-1；++i){

j=i；

for(k=i+1；k<n；++k)

if(a[k]<a[j])j=k；

if(j!=i){w=a[j]；a[j]=a[i]；a[i]=w；}

}//select- sort

(23) A．O(n3)

B．O(n2)

C．O(n)

D．O(n4)

某个应用中，需要对输入数据进行排序，输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下，采用（ ）排序算法最好，时间复杂度为（ ）。

A.插入 B.归并 C.堆 D.快速 A.O(n) B. O(nlgn) C.O(n^2) D. O(n^2lgn)

设使用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)。