使用红宝石中的太空飞船操作员进行自定义排序

Question

我正在实现自定义排序。有一个太空船操作员<=>可以对数组进行排序：

myArray.sort { |a, b| a <=> b }

• a <=> b1当b大于时返回a，并且两个元素被交换。
• a <=> b0当a等于时返回b，并且两个元素保持原始位置。
• a <=> b返回-1when a小于b，并且两个元素保持原始位置。

所以我用一个例子进行了测试：

myArray = [2, 1, 7, 9, 3, 8, 0]
myArray.sort { |a, b| 1 <=> 1 } # making it always return 0
#=> [9, 1, 7, 2, 3, 8, 0]

结果不是我所期望的。在我的期望中，当飞船操作员返回时0，每个元素都将停留在原始位置。由于飞船操作员总是0在以上示例中返回，因此该数组应保持不变。但是，结果与原始数组不同。

我有误会吗？

更新：

以下是我上面的问题来自何处的想法。最初，我试图按对象的属性对对象进行排序（假设属性为status）。

例如

myObjects = [obj1, obj2,..., objn] # the objects are ordered by create_time already

myObjects.sort{|a,b|
    case a.status
        when 'failed'
            x = 1
        when 'success'
            x = 0
        when 'pending'
            x = -1
     end

     case b.status
        when 'failed'
            y = 1
        when 'success'
            y = 0
        when 'pending'
            y = -1
     end

     x <=> y  # compare two objects (a and b) by the status 
}

myObjects已按顺序排序created_time，但我想再次按每个对象的排序status。

例如，

具有相同对象的两个对象created time（此处仅考虑小时和分钟，仅忽略秒）将根据其状态再次排序，从而将具有failed状态的对象置于数组的末尾。

上面代码中的x和y值将取决于对象的状态，并x y进行比较以确定顺序。如果两个对象的状态相同（x == y），则元素应保持在同一位置，因为它们已经按顺序进行created_time了排序，无需再次对其进行排序。

当两个对象的状态都为时success，x <=> y将返回0。但是根据一些评论，0飞船操作员返回的比较值似乎输出了不可预测的顺序。如果myObjects包含状态相同的元素怎么办？自从以来，这将导致飞船操作员始终返回0 x == y。

在我的期望中，myObjects由于状态都相同，应该保持相同的顺序，在这种情况下使用太空飞船操作员该如何纠正？

非常感谢大家的帮助！

Answer 1

您对排序方式的假设不正确。根据文档 #sort不稳定：

结果不能保证是稳定的。当两个元素的比较返回0时，元素的顺序是不可预测的。

Answer 2

Array#sort 使用Quicksort算法，该算法不稳定，并且在元素“相等”时会产生此行为。

原因是在每个步骤都选择和移动枢轴元素，在这种情况下，ruby实现似乎在中间选择了枢轴（但是可以选择不同的方式）。

这是您的示例中发生的情况：

1. 9在数组中间的元素处选择枢轴
2. 现在的算法保证了在左侧的枢轴的项目不到它，在右侧项目是大于或等于，因为一切都是“平等” -这使得一切都在正确的部分
3. 现在对左分区（在这种情况下始终为空）和右分区进行递归重复
4. 结果是sorted_left + [pivot] + sorted_right，左侧为空，因此枢轴移动了

Ruby核心文档中提到了这一点：

当两个元素的比较返回0时，元素的顺序是不可预测的。

同样，太空飞船的运营商<=>在这里不扮演任何角色，您可以要求myArray.sort{0}达到相同的效果。

更新：

从更新的问题中可以明显看出，您想按两个属性进行排序，这可以通过以下几种方法完成：

方法1：您可以发明一个将两个值都考虑在内并按其排序的指标/键：

 status_order = { 'success' => 1, 'failed' => 2, 'pending' => 3 }
 myObjects.sort_by{|o| "#{status_order[o.status]}_#{o.created_time}" }

就极端性能而言，这不是非常理想，但是更短。

方法2：通过编写如下比较规则来隐式组合键：

status_order = { 'success' => 1, 'failed' => 2, 'pending' => 3 }
status_order.default = 0

myObjects.sort{|a,b|
  if a.status == b.status
    a.created_time <=> b.created_time
  else
    status_order[a.status] <=> status_order[b.status]
  end
}