新手的问题，关于排序 — 编程爱好者社区

主题：新手的问题，关于排序

Eniak19 [专家分：0] 发布于 2007-01-16 15:46:00

插入排序、合并排序、堆排序、快速排序这些排序那些是稳定的？

如果是不稳定的，怎么改变着写算法使之能成为稳定的算法呢？

那位高手能谈得具体一点呢？

沙发

xjr1005 [专家分：0] 发布于 2007-01-16 19:26:00

插入排序、合并排序稳定
堆排序、快速排序不稳定

板凳

boxertony [专家分：23030] 发布于 2007-01-17 13:02:00

同上。
另外，既然是不稳定的，那肯定就不能改变乘稳定的，否则就不会称为不稳定的了。

3 楼

Eniak19 [专家分：0] 发布于 2007-01-17 13:38:00

不能么？
如果在每一个成员变量上多加一个域，记录下相同的关键字的数据之间的前后关系，是不是可以呢？
例如

45 6 17 45

只要记录下两个45关键字之间的前后关系？

4 楼

boxertony [专家分：23030] 发布于 2007-01-17 14:14:00

你要这么做的话，自然是可以的；但问题是增加了空间和多了一些操作。

5 楼

Eniak19 [专家分：0] 发布于 2007-01-17 14:42:00

所以我问问，改进后的时间复杂度和空间复杂度都是什么样的？

6 楼

DFDer [专家分：70] 发布于 2007-01-18 00:37:00

时空复杂度不变，只是每次比较时多比一项

7 楼

Eniak19 [专家分：0] 发布于 2007-01-18 15:04:00

不变？你怎么知道只有一组关键字是一样的呢？要是如下的呢

14 2 6 45 14 23 23

你是不是应该先把14和23挑出来呢？时间复杂度不变？

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