算法 数据结构编程（java语言）

private void sort(int[] list)
{
int[] sortlist=new int[21];
for(int i=1;i<=20;i++)
sortlist[i]=-1;
for(int i=0;i<list.Length;i++)
{
sortlist[list[i]]=list[i];
}
for(int i=0;i<sortlist.Length;i++)
{
if(sortlist[i]!=-1)
{
输出sortlist[i];
}
}
因为已知最大值，所以遍历算法计算次数为常数，所以算法复杂度为1追问

CREATE OR REPLACE PROCEDURE ShowCursorVariable

public class test {
public static void main(String[] args) {
int a[]={3,5,9,7,4,13,15,0,2,20};
int temp=0;
for(int i=1;i<a.length;i++){
int j=i-1;
temp=a[i];
for(;j>=0&&temp<a[j];j--){
a[j+1]=a[j];
}
a[j+1]=temp;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}追问

你好 你这样实现 结果时间复杂度不是1啊 谢谢

追答

杀死N亿脑细胞 终于做出来了，单次循环，1复杂度，哈哈：

public class test {

public static void main(String[] args) {
//第一种
int b[] = { 6, 5, 9, 7, 4, 13, 15, 0, 2, 20 };
int i = 0;
int o = 0;
while (o < (b.length - 1) * (b.length - 1)) {
o++;
if (b[i] < b[i + 1]) {
i++;
} else {
b[i] = b[i + 1] + b[i];
b[i + 1] = b[i] - b[i + 1];
b[i] = b[i] - b[i + 1];
i = 0;
}
}
for (int j = 0; j < b.length; j++)
System.out.print(b[j] + ",");
System.out.println();
//第二种
for (int j = 1; j < b.length; j++){
int a = b[j - 1];
if (b[j] < b[j - 1]){
b[j - 1] = b[j];
b[j] = a;
j = 0;
}
}
for (int j = 0; j < b.length; j++)
System.out.print(b[j] + ",");
}
}

本回答被网友采纳

O(1)？不可能吧，就每个数读一遍最少都要 O(n) 吧？我自己想到最好的方法都只是 O(n^2)

如果有一个loop，那已经是 O(n) 。如果loop中有loop，那已经是 O(n^2) 了，就是说
for (....) {
for (...) {
// do something

}
)
单单是这样就已经是 O(n^2) 了

有答案的话，请告诉我，给答案的人应该是神级聪明

我写个大概意思：
int[] x=｛3，5，9，7，4，13，15，0，2，20｝;
int max=20;
string[max] y;
for (int i =0;i<x.length;i++)
{
y[x[i]]=x[i].toString();
}
out=""
for i =0 to max
out+= y[i]+","追问

你好 请问你这个实现后的时间复杂度是为1吗 非常感谢！！

追答

我觉得是.

我坐等，看看哪位神仙能完成……能实现算法复杂度为1的话，他可以拿图灵奖了吧……
光是输出就得O(n)了……追问

不是吧 这个肯定有解决方案的

追答

你要把所有的数字都输出出来，肯定是没有O(1)的方法的。
输出N个数字就要O(n)了。哪来的O(1)啊。
上面那些人要么是没看题目意思，要么就是自己对时间复杂度一点都不了解。