大家说说怎么把tp里面的程序最小化,就是只show桌面?# PDA - 掌中宝
w*1
1 楼
有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂
度O(1),使用交换,而且一次只能交换两个数.(华为)
分析:数组的特点是值和下标满足一定的关系,以此作为交换的终止条件。
但这个算法的时间复杂度如何证明是O(n)呢?
#include
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
for(int i = 0; i < len; )
{
if ( a[i] != i + 1)//下标和值不满足对应关系
{
temp = a[a[i] - 1]; //不相等的话就把a[i]交换到与索引相应的位置
a[a[i] - 1] = a[i];
a[i] = temp;
}
else
i++; // 保存,以后此值不会再动了
}
for (int j = 0; j < len; j++)
cout<return 0;
}
度O(1),使用交换,而且一次只能交换两个数.(华为)
分析:数组的特点是值和下标满足一定的关系,以此作为交换的终止条件。
但这个算法的时间复杂度如何证明是O(n)呢?
#include
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
for(int i = 0; i < len; )
{
if ( a[i] != i + 1)//下标和值不满足对应关系
{
temp = a[a[i] - 1]; //不相等的话就把a[i]交换到与索引相应的位置
a[a[i] - 1] = a[i];
a[i] = temp;
}
else
i++; // 保存,以后此值不会再动了
}
for (int j = 0; j < len; j++)
cout<return 0;
}