C/C++面试之算法系列--1~n无序数组时间复杂度为O(n)排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C/C++面试之算法系列--1~n无序数组时间复杂度为O(n)排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1379字,纯文字阅读大概需要2分钟。
内容图文
转载自:http://blog.csdn.net/sailor_8318/article/details/3054383
1~n无序数组时间复杂度为O(n)排序
有1,2,....一直到n 的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数.(华为)
分析:数组的特点是值和下标满足一定的关系,以此作为交换的终止条件。
但这个算法的时间复杂度如何证明是O(n)呢?
void sortOnorder1(int array[], int len)
{
int temp;
for(int i = 0; i < len; )
{
if ( array[i] != i + 1)//下标和值不满足对应关系
{
temp = array[array[i] - 1]; //不相等的话就把array[i]交换到与索引相应的位置
array[array[i] - 1] = array[i];
array[i] = temp;
}
else
i++; // 保存,以后此值不会再动了
}
}
void sortOnorder2(int array[], int len)
{
int temp;
int i = 0;
for(i = 0; i < len; i++)
{
//不相等的话就把array[i]交换到与索引相应的位置,若相等,其实本次循环没有任何意义,其不会对现有的数据产生任何影响
temp = array[array[i] - 1];
array[array[i] - 1] = array[i];
array[i] = temp;
}
for(i = 0; i < len; i++)
{
temp = array[array[i] - 1]; //不相等的话就把array[i]交换到与索引相应的位置
array[array[i] - 1] = array[i];
array[i] = temp;
}
}
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int b[] = {4,6,9,3,2,8,10,7,1,5};
int lena = sizeof(a) / sizeof(int);
int lenb = sizeof(b) / sizeof(int);
//sortOnorder1(a,lena);
sortOnorder2(a,lena);
for (int j = 0; j < lena; j++)
cout<<a[j]<<",";
cout<<"/n";
//sortOnorder1(b,lenb);
sortOnorder2(b,lenb);
for (int k = 0; k < lenb; k++)
cout<<b[k]<<",";
return 0;
}
原文:http://www.cnblogs.com/lipingLiu/p/3808465.html
内容总结
以上是互联网集市为您收集整理的C/C++面试之算法系列--1~n无序数组时间复杂度为O(n)排序全部内容,希望文章能够帮你解决C/C++面试之算法系列--1~n无序数组时间复杂度为O(n)排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。