ruby - Ruby 排序函数到底做了什么？

Question

首先让我说我是 Ruby 的新手(很明显)。我正在 Codecademy 上学习 Ruby，我对排序功能感到困惑。举个例子:

list = [3,2,1,4]
list.sort { |a,b| b <=> a }

我知道这将按降序返回数组 - [4, 3, 2, 1]。我不明白的是为什么。我知道调用 sort 函数时，数组中的数字被传递到函数中并进行比较，然后函数返回 -1、0 或 1 - 但是然后呢？例如，我猜这是首先要比较的内容:

[3 <=> 2] = 1

但是它对返回的 1 有什么作用呢？得到 1 后数组会是什么样子？

我很困惑，因为我不明白反转比较(a <=> b vs. b <=> a)如何改变数组排序的方向。除非我弄错了，“1 <=> 2”本质上不是返回“1 在 2 之前”，而“2 <=> 1”返回“2 在 1 之后”吗？大同小异，结果却明显不同。

Answer 1

“宇宙飞船”运算符(operator)，<=>不会返回像“a comes before b”这样的英语。它返回什么 sort需要知道:两个元素之间的关系。具体来说，它会返回您提到的 -1、0 或 1 值。

在a <=> b , 如果 a小于 b (通过对 a 是其实例的类使用的任何比较方法)，返回值为 -1。如果相等，则返回 0；如果a大于 b , 返回值为 1。

当你做 b <=> a ，返回值基于b而不是 a ，所以如果 a 更小，你会得到 1，而你在做 a <=> b 时得到 -1 .

因此，虽然英文含义相同，但问题在于细节:即 -1、0 或 1 返回值。该值准确地告诉 Ruby 两个元素如何适合排序数组。

这三个数字的神奇之处在于 quicksort algorithm由 ruby 使用。试图准确解释该算法的工作原理超出了范围，但您基本上可以将其视为对许多值的简单比较。对于数组中的每一项，<=>与数组中的另一个项目一起调用，以确定这两个项目相对于彼此的位置。一旦进行了足够多的比较，所有这些单独项目的位置就已知，排序就完成了。

作为一个简单的(技术上并不准确，但足够接近)示例，请考虑数组 [3, 2, 7, 1] .您可以获取一个值来与其他值进行比较，以便开始排序。我们将选择 3。将 3 与所有其他数字进行比较可以得到:

• 3 <=> 2 == 1 : 3 大于 2，所以 2 必须在 3 的左边。我们的数组现在可能看起来像这样:[2, 3, 7, 1]
• 3 <=> 7 == -1 : 3 小于 7，所以 7 一定是 3 的右边。我们的数组看起来和以前一样，因为 7 已经在右边。
• 3 <=> 1 == 1 : 3 大于 1，所以 1 必须在 3 的左边。我们的数组现在看起来像这样:[2, 1, 3, 7]

我们知道 7 一定是正确的，因为它是“大于 3”这一边的唯一元素。所以我们只需要找出 3 之前的所有内容的排序顺序:1 和 2。运行与上面类似的比较，我们显然交换 1 和 2 以获得 [1, 2, 3, 7]。 .

希望对您有所帮助!