排序算法是否稳定意义很大吗

HateHuyou
HateHuyou 2011-01-17 字数 74

稳定的排序、不稳定的排序,貌似都不影响排序结果,

干嘛还关心其稳定不稳定呢?

Algorithm 算法
9 个回复
Andor
珍惜 2011-01-17

对,如果数据本身就是键,是不影响结果,此时不用关心稳定性。

但当键只是数据的一部分时,影响结果。

例如数据是<任务id,优先级>,按优先级排序时稳定性就很可能很重要。

【 在 HateHuyou () 的大作中提到: 】

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

wxstorm
企鹅 2011-01-17

考虑多字段排序

【 在 HateHuyou () 的大作中提到: 】

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

HateHuyou
HateHuyou 2011-01-17

谢谢楼上,及楼上的楼上

【 在 Andor (柠檬汁) 的大作中提到: 】

: 对,如果数据本身就是键,是不影响结果,此时不用关心稳定性。

: 但当键只是数据的一部分时,影响结果。

: 例如数据是<任务id,优先级>,按优先级排序时稳定性就很可能很重要。

tbe
土豆炖牛肉 => 生煎包 2011-01-17

看股票报价系统

【 在 HateHuyou () 的大作中提到: 】

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

bugbugbug
小虫 2011-01-17

比如实时系统里,只考虑最坏情况,这时候平均就没意义了。

【 在 HateHuyou () 的大作中提到: 】

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

iPush
新的昵称 2011-01-17

这个稳定不是指性能诶

【 在 bugbugbug (小虫) 的大作中提到: 】

: 比如实时系统里,只考虑最坏情况,这时候平均就没意义了。

huoyin
steven 2011-01-21

在次关键字排序时就比较重要。

【 在 Andor (柠檬汁) 的大作中提到: 】

: 对,如果数据本身就是键,是不影响结果,此时不用关心稳定性。

: 但当键只是数据的一部分时,影响结果。

: 例如数据是<任务id,优先级>,按优先级排序时稳定性就很可能很重要。

siyuan98
... 2011-01-27

参照算法导论计数排序部分

【 在 HateHuyou () 的大作中提到: 】

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

Rocket
向Raymond Hettinger学习 2011-03-28

算法导论里面有段相关的,第八章第二节:

An important property of counting sort is that it is stable: numbers with

the same value appear in the output array in the same order as they do in

the input array. That is, it breaks ties between two numbers by the rule

that whichever number appears first in the input array appears first in the

output array. Normally, the property of stability is important only when

satellite data are carried around with the element being sorted. Counting

sort's stability is important for another reason: counting sort is often

used as a subroutine in radix sort. As we shall see in the next section,

in order for radix sort to work correctly, counting sort must be stable.

【 在 HateHuyou () 的大作中提到: 】

: 标  题: 排序算法是否稳定意义很大吗

: 发信站: 水木社区 (Mon Jan 17 14:33:24 2011), 站内

: 稳定的排序、不稳定的排序,貌似都不影响排序结果,

: 干嘛还关心其稳定不稳定呢?

: --

: 几乎所有好姑娘,轰轰烈烈,翻云覆雨,曾经沧海之后,想想自己的后半生,想想也无风雨也无晴,想要找个老实孩子嫁掉,就会想起清华男生。。。。