简单一道排序题，考倒多少读书人

标签： 排序 读书人 | 发表时间：2011-09-20 17:12 | 作者：漫长路 小明
出处：http://www.cnblogs.com/

 

从华为一道面试题来看看吧，原题大意是这样的：
 

 

　　有N个大小不等的自然数（1--N），请将它们由小到大排序。
 　  要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
      (请你做做看，时间20分钟）

 

 有人这样做：

void sort(int e[], int n)
{
 int i;
 int t; /*临时变量：空间复杂度O(1)*/

 for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
 {
  t = e[e[i]]; /*下标为e[i]的元素，排序后其值就是e[i]*/
  e[e[i]] = e[i];
  e[i] = t;
 }
}

void main()
{ 
 #define MAX 10
 int i, a[MAX+1]; 
 
 printf("Input the number from 1 to %d:/n",MAX);
 for (i=1; i<MAX+1; i++)
 {
  scanf("%d",&a[i]);
 }
  
 sort(a,MAX);

 printf("/n====sort over====/n");
 for (i=1; i<MAX+1; i++)
 {
  printf("%d ",a[i]);
 }

 printf("/n");
 system("pause");
}

 

上述答案其实是不对的，请看下面：

void sort(int e[], int n)
{
int i;
int t; /*临时变量：空间复杂度O(1)*/

for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
{
while(e!=i)
{
   t = e[e]; /*下标为e的元素，排序后其值就是e*/
   e[e] = e;
   e = t;
}
}

 这个while 实在是太强大了，心血沸腾，于是赶紧记录之。

作者: 漫长路 发表于 2011-09-20 17:12 原文链接

评论: 2　查看评论　发表评论

最新新闻：
· 纸质名片杀手Cardcloud推出Android应用(2011-09-20 17:43)
· 消亡的是桌面操作系统，而非台式机(2011-09-20 17:40)
· Ruby on Rails 3.1发布了，带来了资产管道、流和JavaScript的改变(2011-09-20 17:32)
· 魅族MX首张官方图曝光 M9降价为其开道(2011-09-20 17:18)
· Team Foundation Server 11中的应用生命周期管理(2011-09-20 17:15)

编辑推荐：忘记敏捷

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [排序 读书人] 推荐：

简单一道排序题，考倒多少读书人

- 小明 - 博客园-首页原创精华区
从华为一道面试题来看看吧，原题大意是这样的：. 　　有N个大小不等的自然数（1--N），请将它们由小到大排序.  　  要求程序算法：时间复杂度为O(n)，空间复杂度为O(1).       (请你做做看，时间20分钟）.  int t; /*临时变量：空间复杂度O(1)*/.  for (i=1; i

堆排序

- kongshanzhanglao - 博客园-首页原创精华区
       堆排序是利用堆的性质进行的一种选择排序.   堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：.   Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2].   即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字.

排序算法

- - 互联网 - ITeye博客
排序算法有很多，所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法，可以按照建议的顺序考虑以下标准： .     对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要.  一、冒泡（Bubble）排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

lucene排序

- - 开源软件 - ITeye博客
排序是对于全文检索来言是一个必不可少的功能，在实际运用中，排序功能能在某些时候给我们带来很大的方便，比如在淘宝，京东等一些电商网站我们可能通过排序来快速找到价格最便宜的商品，或者通过排序来找到评论数最高或卖的最好的商品，再比如在Iteye里的博客栏里，每天都会以降序的方式，来显示出最新发出的几篇博客，有了排序，我们就能在某些时候很方便快速的得到某些有效信息，所以说排序功能，无处不在 ^_^.

【原】MapReduce的排序和二次排序

- - ITeye博客
自己学习排序和二次排序的知识整理如下. 1.Hadoop的序列化格式介绍:Writable. 2.Hadoop的key排序逻辑. 4.如何自定义自己的Writable类型. 1.Hadoop的序列化格式介绍:Writable. 要了解和编写MR实现排序必须要知道的第一个知识点就是Writable相关的接口和类，这些是HADOOP自己的序列化格式.

Java排序算法：归并排序

- - zzm
 Java排序算法（九）：归并排序. 归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 归 并排序是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用.

排序大比武

- niko - C++博客-首页原创精华区
     摘要: 该比武只比速度，单线程测试随机正整数，不包括蜗牛排序，它弃权啦，哈哈. 操作系统：Windows XP Pro SP3，英文版编译器：g++4.5.2(-O3)CPU： Intel Core2 Q9500内存：DDR3普条 1066MHz， 4GB 插入排序、选择排序和冒泡排序最慢，时间复杂度为O(n2)，希尔排序的速度依赖于使用的增量序列，堆排序、归并排序和改进的快速排序处于中等水平，时间复杂度...  阅读全文.

hadoop 二次排序

- - 企业架构 - ITeye博客
hadoop的工作流程：. 是在key中，排序value的实现，思路是. 1.把value中需要有序的部分value-part放入key中. 2.sortCompare类或key的CompareTo方法中完成对key+value-part的比较. 3.GroupingCompare中只对key进行比较，这样相同的key跌倒获取到reduce中.

排序算法 Sleep Sort

- Jeff - 酷壳 - CoolShell.cn
排序算法好像是程序员学习编程最多的算法，也可能是算法研究者们最喜欢研究的算法了. 排序有很多很多的算法，比如，冒泡，插入，选择，堆，快速，归并等等（你可以看看本站以前的那些文章：可视化的排序，排序算法比较，显示排序过程的python）这里向大家介绍一个“巨NB”的排序算法——Sleep Sort. 闲言少说，请看下面的代码（用Shell脚本写的）.

“天才”排序算法：Sleepsort

- Sirius - 黑客志
4chan上某位神人发明的天才排序算法：Sleepsort，充分发挥多核威力，评论中还有更多优化版本：. TermKit: 下一代的Mac命令行/终端程序.