为三个整数排序

采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数己经排好序，将第i个整数依次和第i-1, i-2, ...个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序，则需要进行（31）次整数之间的比较。对于该排序算法，输入数据具有（32）特点时,对整数进行从小到大排序，所需的比较次数最多。

A.9

B.10

C.12

D.13

●下面算法是实现对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)

下面算法是实现对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)

下面算法是实现对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)

请补充main函数，该函数的功能是：把一个整数插入一个已经按从小到大排序的数组中。插入后，数组仍然有序。 例如，在数组bb[M]={10 20 30 40 50 60 70 80 85 95} 中插入75，结果为 bb[M]={10 20 30 40 50 60 70 75 80 85 95} 注意：部分源程序给出如下。 请勿改动main函数和其他函数中的任何内容，仅在main函数的横线上填入所编写的若干表达式或语句。 试题程序： include<stdlib．h> include<stdio．h> define M 10 void main { int i，j； int n； int bb[M+1]={10，20，30，40，50，60，70，80，85，95}； system("CLS")； printf("＼nlnput n n")； scanf("％d"，＆n)； printf("＼nn=％d"，n)； printf("＼n***original list***＼n")； for(i=0；i<M；i++) printf("％4d"，bb[i])； for(i=0；i<M；i++) { if(n<=bb[i]) { for(j==M；【1】 ；j--) 【2】 ； bb[j]=n； 【3】 ； } } if(i==M) bb[i]=n： printf("＼n****new list****＼n")； for(i=0；i<M+1；i++) printf("％4d"，bb[i])； }

已知有8个整数：1，7，3，2，0，5，6，8，分别用下列方法进行排序，编写程序。

  (1)直接插入排序；

  (2)折半插入排序；

  (3)希尔排序。

下列给定程序中fun()函数的功能是：将n个无序整数从小到大排序。

请改正程序中的错误，使它能得出正确的结果。

注意；不要改动main函数，不得增行或删行，也不得更改程序的结构。

试题程序：

include ＜conio.h＞

include ＜stdio.h＞

include ＜stdlib.h＞

fun(int n, int *a)

{ int i,j,p,t;

for (j=0;j＜n-1;j++)

{ P=j;

/***************found*******************/

for(i=j+l;i＜n-1;i++)

if (a[p]＞a[i])

/***************found*******************/

t=i;

if (p!=j)

{t=a[j];a[j]=a[p];a[p]=t;}

}

}

putarr( iht n,int *z)

{int i;

for (i=l;i＜=n;i++,z++)

{ printf("%4d",*z);

if (!(i%10)) printf("\n");

} printf ("\n");

}

main ()

{int aa[20]={9,3,0,4,1,2,5,6,8,10,7},n=11;

clrscr();

printf("\n\nBefore sorting %d numbers:\n",n); putarr(n,aa);

fun(n,aa);

printf("\nAfter sorting %d numbers:\n",n);putarr(n,aa);

}

叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)【南京航空航天大学2000一】

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序， 最终得到非递减的有序序列。 函数 quicksort(int a[]，int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素 a[0]-a[n-1]中。

【C 代码】 include < stdio.h> void quicksort(int a[] ，int n) { int i ，j; int pivot = a[0]; //设置基准值 i =0; j = n-l; while (i< j) { while (i<j &&（1）) j-- //大于基准值者保持在原位置 if (i<j) { a[i]=a[j]; i++;} while (i,j &&（2）) i++; //不大于基准值者保持在原位置 if (i<j) { a[j]=a[i]; j--;} } a[i] = pivot; //基准元素归位 if ( i>1) （3） ; //递归地对左子序列进行快速排序 if ( n-i-1>1 ) （4） ; //递归地对右子序列进行快速排序 } int main () { int i，arr[ ] = {23，56，9，75，18，42，11，67}; quicksort ( （5） ); //调用 quicksort 对数组 arr[ ]进行排序 for( i=0; i<sizeof(arr) /sizeof(int); i++ ) printf(" %d\t" ，arr[i]) ; return 0; }