刚看到的一个排序算法题，大家讨论讨论。

tyc611

原帖由 bleem1998 于 2006-12-28 20:52 发表
能否照顾一下我这个数据结构盲
请说明一下什么是"O(1)的辅助空间"
3Q

指需要的辅助空间为常数大小（在算法确定时就确定了，不会随着问题规模改变而改变，跟时间复杂度类似）

tyc611

原帖由 bleem1998 于 2006-12-28 21:07 发表
我觉得这个题目是很有深意的
这个数组就像一个大公司
每个位置代表一个职位
那些重复的数字代表正在做着同样重复工作的员工
现在要把这个大公司拆分成若干小公司
小公司里大家各司其职没有重复
： ）
发下 ...

想得不错

bleem1998

原帖由 tyc611 于 2006-12-28 22:48 发表

指需要的辅助空间为常数大小（在算法确定时就确定了，不会随着问题规模改变而改变，跟时间复杂度类似）

受教了
但似乎不太够啊
请问网上有没有什么资料是讲这个的?
经常看到有什么时间复杂度O(X)什么的
不明白是什么意思啊
我的数据结构书上也没解释
这样让我感觉自己非常的土

nasi

原帖由 bleem1998 于 2006-12-28 23:16 发表


受教了
但似乎不太够啊
请问网上有没有什么资料是讲这个的?
经常看到有什么时间复杂度O(X)什么的
不明白是什么意思啊
我的数据结构书上也没解释
这样让我感觉自己非常的土

通常算法分析的书籍一上来就讲这个，比如《算法导论》之类的书

ArXoR

原帖由 tyc611 于 12/28/06 22:48 发表

指需要的辅助空间为常数大小（在算法确定时就确定了，不会随着问题规模改变而改变，跟时间复杂度类似）

确切的说这个也不对。。。
是存在一个常数上界。。。需要的空间不一定是常数

namtso

原帖由 ArXoR 于 2006-12-29 11:37 发表


确切的说这个也不对。。。
是存在一个常数上界。。。需要的空间不一定是常数

不是常数上界的，是不是算做O（n）啊？

ArXoR

原帖由 namtso 于 12/29/06 12:16 发表

不是常数上界的，是不是算做O（n）啊？

不是...不是常数的函数多了去了...

ArXoR

原帖由 emacsnw 于 12/28/06 16:33 发表
给你一个已经排好序的数组a，里面可能有重复元素，比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1}，要求里面的每个子序列都是有序的，并且其中的元素唯 ...

如果数组是浮点数, 但是题目保证输入都是整数的话, 利用小数部分保存信息可以做到O(n)...
但是有点cheat了...

bleem1998

想了一个算法
只需要一个交换变量就可以了
排序过程是这样的

1. 
   
2. 1, 1, 1, 2, 3, 3, 4, 5, 5
   
3. 1, 2, 1, 1, 3, 3, 4, 5, 5
   
4. 1, 2, 3, 1, 1, 3, 4, 5, 5
   
5. 1, 2, 3, 4, 1, 3, 1, 5, 5
   
6. 1, 2, 3, 4, 5, 3, 1, 1, 5
   
7. 1, 2, 3, 4, 5, 1, 3, 1, 5
   
8. 1, 2, 3, 4, 5, 1, 3, 5, 1
   

复制代码

排序规则如下

1. 
   
2. a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5};
   
3. int part_ok = 0;
   
4. for (i = 1; i < sizeof(a)/sizeof(a[0]); i++) {
   
5.         //查找a[i-1]后面第一个比a[i-1]大的数
   
6.         //如果遇到比a[i-1]小的数，如果park_ok==1则交换那个数和a[i-1]的位置，park_ok=1,i--,continue
   
7.         //如果找到比a[i-1]大的，则交换这个数和a[i]的位置，park_ok=0, continue
   
8.         //如果找不到，park_ok=1,i++,continue    (这说明其中一个小分公司已经建好)
   
9. 
   
10. }
    

复制代码

[ 本帖最后由 bleem1998 于 2006-12-29 13:46 编辑 ]

tyc611

原帖由 bleem1998 于 2006-12-29 13:20 发表
想了一个算法
只需要一个交换变量就可以了
排序过程是这样的
[code]
1, 1, 1, 2, 3, 3, 4, 5, 5
1, 2, 1, 1, 3, 3, 4, 5, 5
1, 2, 3, 1, 1, 3, 4, 5, 5
1, 2, 3, 4, 1, 3, 1, 5, 5
1, 2, 3, 4, 5, 3, 1,  ...

你这样做，第一遍之后就把剩下的子序列打乱了，不知道你怎么处理剩下的