排序算法在处理组合数据类型数组时是否表现出更大的不稳定性?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (79)

或者稳定性与处理原始数据类型数组时相同?

提问于
用户回答回答于

关于问题是关于稳定性和对基元与对象进行排序的可能性,那么在一些编译器语言的情况下,快速排序的变体用于基元,这是不稳定的,而合并排序的变体用于对象。很稳定。这是因为如果对基元进行排序,稳定性通常不是问题。

使用原始整数类型检测稳定性的一种方法是使用整数的一部分作为原始序列值,并使用仅比较其他部分的自定义比较。也许对于32位整数,高16位填充随机数据并用于比较,低16位用作原始序列指示符。

用户回答回答于

当按原始值的实际完整值对原始值数组进行排序时,稳定性的概念并不真正相关。

如果你有一个数组[2,1,3,2]并对它进行排序,那么你得到[1,2,2,3]。无论你使用稳定排序还是不稳定排序,结果都完全相同。

当你没有按完整值排序时,即当比较相等的项目实际上不同时,稳定性变得相关。例如,如果你用它们的数字之和对整数数组进行排序,那么[11,5,13,​​22]将变为[11,13,22,5]并且具有稳定的排序,但是不稳定的排序可能会给输出[11,22,13,5]

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动