一个排序算法 — 编程爱好者社区

主题：一个排序算法

ztj111 [专家分：0] 发布于 2008-03-12 11:39:00

设有N个元素的数组包含三个不同的关键字true、false和maybe。给出一个O(N)算法，重新排列这些元素，使得所有false的元素都排在maybe元素的前面，而maybe元素都排在true元素的前面。你只能用到使用常数附加空间。

沙发

bpttc [专家分：8790] 发布于 2008-03-12 16:35:00

啊，楼主的算法在哪？

板凳

lpf46261479 [专家分：970] 发布于 2008-03-12 21:45:00

x=strlen(n)
sort(n,n+x);

3 楼

justforfun626 [专家分：18460] 发布于 2008-03-13 00:18:00

[quote]啊，楼主的算法在哪？[/quote]

楼主的算法 is in the eyes of children. (from an old old song...[em2])

4 楼

neulinux [专家分：420] 发布于 2008-03-13 00:58:00

首先，个人觉得这个问题很。。。
因为如果不是限制排序方法的话，由于值域是可枚举的，直接对N个元素的数组扫描一遍，对于各个分立值的个数计数，然后按照要求顺序重新写入数组就可以了，必然是O(N)的啊！

5 楼

天之痕99 [专家分：40] 发布于 2008-03-18 11:33:00

这还不容易？
头尾各一个指针，往中间移动，把找到的true全换到左边；一遍过后再把头指针放在true的末尾，和尾指针一起再来一遍，把false交换到右边。O(N)搞定！

您尚未登录，请登录后再回复。点此登录或注册