设任意n个整数存放于数组A（1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0（n)）。 [题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。
设任意n个整数存放于数组A（1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0（n)）。 [题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。
参考答案和解析
[算法描述]void Arrange(int A[],int n) //n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面{int i=0,j=n-1,x; //用类C编写，数组下标从0开始while(i{while(i0) i++;while(i if(i交换A[i] 与A[j]}// while(i}//算法Arrange结束.[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1).
相关考题：
●已知有二维数组A［0．．n-1］［0．．n-1］，其中当i+j=n时，A［i］［j］≠0，现在要将A数组压缩存储到一维数组T［0..m］，其中mn。数组T的第一个元素T［0］=A［1］［n-1］ T［1］=A［2］［n-2］，……，依次类推，那么放入A［i］［j］(i+j=n)的元素是 (37) 。(37) A．T［i+j］B．T［i*n+j］C．T［i］D．T［i-1］
试题二（共 15分）阅读以下说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明 1】函数Counter(int n, int w[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3，在w[0]中存入2（即21）、w[1]中存入4（即22）、w[2]中存入16（即24）。【C函数 1】int Counter(int n, int w[]){ int i = 0, k = 1;while ( （1） ) {if (n % 2) w[i++] = k;n = n / 2; （2） ;}return i;}【说明 2】函数 Smove(int A[], int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为：设置数组元素下标索引i（初值为0）和j（初值为n-1），从数组的两端开始检查元素的奇偶性。若 A[i]、A[j]都是奇数，则从前往后找出一个偶数，再与 A[j]进行交换；若 A[i]、A[j]都是偶数，则从后往前找出一个奇数，再与A[i]进行交换；若 A[i]是偶数而A[j]是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。【C函数 2】void Smove(int A[], int n){ int temp, i = 0, j = n-1;if ( n 2 ) return;while ( i j ) {if ( A[i] % 2 == 1 A[j] % 2 == 1 ) { （3） ; }else if ( A[i] % 2 == 0 A[j] % 2 == 0 ) { （4） ; }else {if ( （5） ) {temp = A[i]; A[i] = A[j]; A[j] = temp;}i++, j--;}}}
●下面算法是实现对n个整数的序列进行选择排序，其中序列的"长度"n为问题的规模。该算法的时间复杂度为 (23) 。void select_sort(int a[]，int n){//将a中整数序列重新排列成从小到大有序的整数序列for(i=0；in-1；++i){j=i；for(k=i+1；kn；++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)
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置，InsertSort 类的成员函数sort（）实现了插入排序算法，请将画线处缺失的部分补充完整。class InsertSort{public:InsertSort（int*a0,int n0）:a（a0）,n（n0）{}//参数组首地址，n 是数组元素个数void sort（）{//此函数假设已排离序列初始化状态只包含a[0]，未排序序列初始为a[1]?a[n-1]for （int i=1;iint j;for（ [14] j0;--j）{if（ta[j-1]）break;a[j]=a[j-1];}a[j]=t;}}protected:int*a,n;//指针a 用于存放数组首地址，n 用于存放数组元素个数}；
设二维数组A[1...m，1...n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为()。A.n*（i－1）＋jB.n*（i－1）＋j－1C.i*（j－1）D.j*m＋i－1
（ 14 ） 插入排序算法的主要思想是 ： 每次从未排序序列中取出一个数据 ， 插入到已排序序列中的正确位置 。InsertSort 类的成员函数 sort() 实现了插入排序算法。请将画线处缺失的部分补充完整。class InsertSort{public:InsertSort(int* a0, int n0) :a(a0), n(n0) {} // 参数 a0 是某数组首地址， n 是数组元素个数void sort( ){// 此函数假设已排序序列初始化状态只包含 a[0] ，未排序序列初始为 a[1]...a[n-1]for (int i=1; iint t=a[i];int j;for ( 【 14 】 ; j0; --j){if (t=a[j-1]) break;a[j]=a[j-1];}a[j]=t;}}protected:int *a, n; // 指针 a 用于存放数组首地址， n 用于存放数组元素个数};
阅读下列程序说明和C代码，把应填入其中n处的字句写在答卷的对应栏内。【说明】程序利用选择排序算法对数组a中的N个整数按照从小到大的顺序排列，并将排序结果显示出来。【程序】define N 10main(){void (1)；int i，a[N]；for(i=0；i＜10，i++) /*输入*/scanf(“%d”，a[i])；(2)；for(i=0；i＜N，i++) /*输出*/printf(“%3d”，a[i])；}void selectSon(int x[]，int n){int i，j，k，t；for(int i=0； (3)；i++){k=i；for(j=i+1；j＜n；j++)if (4) k=j；if (5){t=x[i]；x[i]=x[k]；x[k] =t；}}}
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入已排序序列中的正确位置。Insert类的成员函数sort()实现了插入排序算法，请填空。class Insert{public:Insert(int*b0,int n0):b(b0),n(n0){};//参数b0是某数组首地址，n是数组元素个数void sort(){//此函数假设已排序序列初始化状态只包含b[0]，未排序序列初始为b[1]…b[n-1]for(int i=1;i＜n;++i){int t=b[i];int j;for(______;j＞0;--j){if(t＞=b[j-1])break;b[j]=b[j-1];b[j]=t;}}}};
● 设数组a[0..m,1..n]的每个元素占用1个存储单元，若元素按行存储，则数组元素a[i,j]（0≤i≤m，1≤j≤n）相对于数组空间首地址的偏移量为 （32） 。（32）A. (i+1)*n+jB. i*n+j-1C. i*m+jD. i*(m+1)+j-1
●设数组a[1．．n，1．m](n1，m1)中的元素以行为主序存放，每个元素占用1个存储单元，则数组元素a[i，j](1≤i≤n，1≤j≤m)相对于数组空间首地址的偏移量为(14)。(14) A. (i-1)*m+j-1B. (i-1)*n+j-1C. (j-1)*m+i-1D. (j-1)*n+i-1
设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为()。 A.(i-1)*n+jB、(i-1)*n+j-1C.i*(j-1)D、j*m+i-1
插入排序算法的主要思想：每次从未排序序列中取出一个数据，插入到已排序序列中的正确位置。Insert类的成员函数sort()实现了插入排序算法，请填空。class Insert{public:Insert(int *b0,int n0):b(b0),n(n0)＜);//参数b0是某数组首地址，n是数组元素个数void sort(){//此函数假设已排序序列初始化状态只包含b[0]，未排序序列初始为b[1]...b[n-1]for(int i=1;i＜n;++i){int t=b[i];int j;for(______;j＞0;--j){if(t＞=b[j-1])break;b[j]=b[j-1];b[j]=t;}}}
下面算法是实现对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_sortA．O(n2)B．O(n3)C．O(n4)D．O(n)
插入排序算法的主要思想是：每次从未排序序列中取出一个数据，插入到己排序序列中的正确位置。InsertSort类的成员函数sort()实现了插入排序算法。请将画线处缺失的部分补充完整。class InsertSort{public：InsertSort(int* a0，int n0)：a(a0)，n(n0){}//参数a0是某数组首地址，n是数组元素个数void sort(){//此函数假设已排序序列初始化状态只包含a[0]，未排序序列初始为a[1]…a[n-1]for(int i=1；i＜n；++i){int t=a[i]；int j；for(【 】;j＞0；--j){if(t＞=a[j-1])break；a[j]=a[j-1]；}a[j]==t；}}protected：int*a，n；//指针a用于存放数组首地址，n用于存放数组元素个数};
设数组a[0．．m，1．．n]的每个元素占用1个存储单元，若元素按行存储，则数组元素a[i，j](0≤i≤m，1≤j≤n)相对于数组空间首地址的偏移量为( )。A．(i+1)*n+jB．i*n+j-lC．i*m+jD．i*(m+1)+j-1
本题的功能是用冒泡法对数组元素arr[]={30，1，-9，70）进行从小到大排列。冒泡法排序是比较相邻的两个元素的大小，然后把小的元素交换到前面。public class javal{public static void main（String[]args）{int i，j；int arr[]={30，1，-9，70）；int n= ；for（i=0；i<；n-1；i++）{for（j=i+1；j<；n；j++）{if（arr[i]>；arr[j]）{int temp=arr[i]；；；}}}for（i=0；i<；n；i++）System．out．print（arr[i]+""）；}}
已知有二维数组A[0..n-1][0..n-1]，其中当i+j=n时，A[i][j]≠0，现在要将A数组压缩存储到一维数组T[0..m]，其中m＞n。数组T的第一个元素T[0]=A[1][n-1] T[1]=A[2][n-2]，……，依次类推，那么放入A[i][j](i+j=n)的元素是(37)。A．T[i+j]B．T[i*n+j]C．T[i]D．T[i-1]
设数组a[0．n-1,0．．m-1](n1，m1)中的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j](0in，0jm)的存储位置相对于数组空间首地址的偏移量为 （ ）。A.(j*m+i)*4B.(i*m+j)*4C.(j*n+i)*4D.(i*n+j)*4
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：待排序数组 p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r begin,end：待排序数组的起止位置 left,right：临时存放待合并的两个子数组 n1,n2：两个子数组的长度 i,j,k：循环变量 mid：临时变量 【C代码】inciudestdio.h inciudestdlib.h define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror(malloc error); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror(malloc error); exit(1); } for(i=0;in1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; in2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; （1） ; k++) { if(left[i] right[j]) { （2） ; j++; }else { arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if( （3） ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4） ; merge(arr,begin,mid,end); } }【问题1】 根据以上说明和C代码，填充1-4。 【问题2】 根据题干说明和以上C代码，算法采用了（5）算法设计策略。 分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。
设数组a[0..n-1，0..m-1](n＞1，m＞1)中的元素以行为主序存放，每个元素占用1个存储单元，则数组元素a嘶](0＜i＜n,0＜j＜m)的存储位置相对于数组空间首地址的偏移量为( )。A.j*m+iB.i*m+jC.j*n+iD.i*n+j
设数组a[1..m,1..n]（m＞1，n＞1）中的元素按行存放，每个元素占用1个存储单元，则数组元素a[i,j]（1≤i≤m，1≤j≤n）相对于数组首元素的偏移量为（ ）。A.(i-1)*m+j-1B.(i-1)*n+j-1C.(j-1)*m+i-1D.(j-1)*n+i-1
设数组a[0..n-1,0..m-1](n>1，m>1)中的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j](0≤iA. (j*m+i)*4B.(i*m+j)*4C.(j*n+i)*4D.(i*n+j)*4
设数组a[1..n，1..m]（n>1，m>1）中的元素以行为主序存放，每个元素占用1个存储单元，则数组元素a[i，j]（1≤i≤n,i≤j≤m）相对于数组空间首地址的偏移量为（ ）。A.（i-1）*m+j-1B.（i-1）*n+j-1C.（j-1）*m+i-1D.（j-1）*n+i-1
设数组a[1..n，1..m]（n>l，m>l）中的元素以行为主序存放，每个元素占用1个存储单元，则数组元素a[i，j]（1≤i≤n,i≤j≤m）相对于数组空间首地址的偏移量为（14）。A.（i-1）*m+j-1B.（i-1）*n+j-1C.（j-1）*m+i-1D.（j-1）*n+i-1
设数组a[0..n-1，0..m-1]（n>0，m>0）中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素a[i，j]（0≤i≤n-1,0≤j≤m-1）相对于数组空间首地址的偏移量为（ ）。A.i*m+jB.（i-1）*n+j-1C.j*n+iD.（j-1）*n+i-1
设顺序表共有n个元素，用数组elem存储，实现在第i个元素之前插入一个元素e的操作，其主要语句为（）。A、FOR j=n DOWNTO i DO elem[j]=elem[j+1]； elem[i]=e；B、FOR j=i TO n DO elem[j]=elem[j+1]； elem[i]=e；C、FOR j=i TO n DO elem[j+1]=elem[j]； elem[i]=e；D、FOR j=n DOWNTO i DO elem[j+1]=elem[j]； elem[i]=e；
设二维数组A[1„m，1„n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为（）。A、n*（i－1）＋jB、n*（i－1）＋j－1C、i*（j－1）D、j*m＋i－1