对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为（）。
问题
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计
参考解析：
本题需要用3个辅助变量n1、n2和n3来保存数组A中-1、0和1的个数，空间复杂度为Θ（1）。在统计时，需要使用一循环语句遍历数组A。统计完成后，再使用一次循环语句遍历数组A，并将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n个元素赋值为1。数组A的元素个数为n，因此算法的时间复杂度为Θ（n）。
分类：算法设计和分析题库,中级软件设计师题库
相关推荐
-
1、● 设数组a[0..m,1..n]的每个元素占用1个存储单元，若元素按行存储
● 设数组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
-
2、设有以下语句，其中不是对a数组元素的正确引用的是______（其中0≤i＜1
设有以下语句，其中不是对a数组元素的正确引用的是______（其中0≤i＜10) int a[10]={0,1,2,3,4,5,6,7,8,9,},*p=a;Aa[p-a]B*(&a[i])Cp[i]D*(*(a+i))
-
3、对于二维数组a[0..4,1..5]，设每个元素占1个存储单元，且以行为主序
对于二维数组a[0..4,1..5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,1]相对于数组空间起始地址的偏移量是(40)。A5B10C15D25
-
4、设数组a[0．．m，1．．n]的每个元素占用1个存储单元，若元素按行存储，则
设数组a[0．．m，1．．n]的每个元素占用1个存储单元，若元素按行存储，则数组元素a[i，j](0≤i≤m，1≤j≤n)相对于数组空间首地址的偏移量为( )。A(i+1)*n+jBi*n+j-lCi*m+jDi*(m+1)+j-1
-
5、已知一个大小为n的整型数组，现求该数组的全部连续子数组的元素之和的最大值，最
已知一个大小为n的整型数组，现求该数组的全部连续子数组的元素之和的最大值，最优算法的时间复杂度是()如：a[4]={2,-1,3,-4}，它的全部连续子数组为{2,-1,3,-4,[2,-1],[-1,3],[...
-
6、设a、b、c为整型变量，其值分别为1、2、3，以下程序段的输出结果是（）a=
设a、b、c为整型变量，其值分别为1、2、3，以下程序段的输出结果是（）a=b：b=c：c=aPrinta；b；cA123B231C321D232