使用Sort和Sort_by对数组进行排序

Question

我试图围绕下面的代码如何工作来构建一个心理模型，但它让我感到困惑。我正在尝试对字符串进行排序，以便每个重复的字母都在一起，但大写字母排在第一位。它已经解决了，下面的方法可以解决它，但我想知道为什么你必须先sort它？它是否保持与第一次排序相同的位置？因此，当您调用sort_by时，它会按小写字母排序，但大写字母仍保留在原来的位置？有没有人可以一步一步地分析正在发生的事情，这样我才能更好地理解它？

def alpha(str)
 str.chars.sort.sort_by { |ele| ele.downcase }.join
end

alpha("AaaaaZazzz") == "AaaaaaZzzz"

Answer 1

不能依赖于Ruby中排序的稳定性

这是一个有趣的问题。一个排序是否保持相等元素的顺序是它的“稳定性”。如果保证保持相等元素的顺序，则排序是稳定的；如果没有这样的保证，则排序是不稳定的。不稳定的排序可能会按原始顺序返回相等的元素，也可能不返回。

在MRI 2.7.1中，sort碰巧是稳定的，但它实际上是由实现定义的。有关所有有趣的细节，请参见https://stackoverflow.com/a/44486562/238886，其中包括可以在Ruby中运行的代码，以了解您的排序是否恰好是稳定的。但是不管你的排序是否稳定，你都不应该依赖它。

稳定的排序确实会返回预期的结果，而且无论是否包含.sort，它都会返回

2.7.1 :035 > "AaaaaZazzz".chars.sort_by { |ele| ele.downcase }.join
 => "AaaaaaZzzz" 
2.7.1 :036 > "AaaaaZazzz".chars.sort.sort_by { |ele| ele.downcase }.join
 => "AaaaaaZzzz" 

但是你可以在需要的时候让排序变得稳定

为了不依赖于排序的稳定性，当你将你的代码转移到另一个Ruby版本或实现时，这种稳定性可能会改变，你可以像这样强制稳定性：

 "AaaaaZazzz".chars.sort_by.with_index { |ele, i| [ele.downcase, i] }.join
 => "AaaaaaZzzz" 

不稳定排序是如何表现的？

我们可以通过添加一个随机数作为第二排序顺序来强制Ruby 2.7.1的排序不稳定：

2.7.1 :040 > "AaaaaZazzz".chars.sort.sort_by { |ele, i| [ele.downcase, rand] }.join
 => "AaaaaaZzzz" 
2.7.1 :041 > "AaaaaZazzz".chars.sort.sort_by { |ele, i| [ele.downcase, rand] }.join
 => "aaaaAazzZz" 

请注意，我们是如何在第一次得到与稳定排序相同的答案，但随后得到了不同的答案？这演示了不稳定排序是如何偶然给出与稳定排序相同的结果的。但你不能指望它。

Answer 2

首先，在此代码中，根据底层编码的排序顺序按字母顺序对所有字符进行排序，然后以大小写字符同等对待的方式对字符进行排序。这取消了第一个排序的效果。因此，输出等同于str.chars.sort_by(&:downcase)，这将是编写表达式的一种更明智的方式。

第一个sort没有作用，因此只是一个周期窃取程序。顺便说一下:由于Ruby排序的稳定性未指定，特别是众所周知的MRI Ruby是不稳定的，因此您无法控制在排序顺序中被认为是等价的单个字符的相对顺序。还要注意，结果取决于区域设置，因为这决定了字母Б和б在排序顺序上是相同还是不同。