Lua table.sort调用相同元素的比较函数

Question

我偶然发现了

table.sort()

的奇怪行为，其中通过在两个参数中传递相同的数组元素来调用比较函数。

考虑下面的代码。我想按属性

v

的最高值到最低值对数组进行排序，并且，如果它们相等（并且由于

table.sort()

算法截至 文档 并不稳定），我想按原始值对它们进行排序元素的索引。

-- The array to sort
local arr = {
  {id="A", v = 1},
  {id="B", v = 1},
  {id="C", v = 0},
  {id="D", v = 1},
  {id="E", v = 1}
}

-- A map containing the original index of the elements in the array: element => originalIndex
local original_indices = {}
for index, elem in ipairs(arr) do
  original_indices[elem] = index
end

-- Sort the array
table.sort(arr, 
  function(a, b) 
    assert(a ~= b, "Comparing the same element in the array!")
    
    -- Compare the value
    if a.v > b.v then
      return true
    elseif a.v < b.v then
      return false
    end
    
    -- Values are equal. Compare original indices, which should always
    -- decide the final order.
    local ia = original_indices[a]
    local ib = original_indices[b]
    
    if ia < ib then
      return true
    elseif ia > ib then
      return false
    end
    
    error("BUG! Comparing the same element in the array!") 
  end
)

预期结果应该是：

{  
  {id="A", v = 1},
  {id="B", v = 1},
  {id="D", v = 1},
  {id="E", v = 1},
  {id="C", v = 0}
}

但是，我收到了一个错误，因为 Lua 通过在两个参数中传递相同的元素来调用排序函数，而这是不应该的。

我错过了什么吗？怎样才能得到预期的结果？

您可以在这里使用代码。

Answer 1

要解决您的问题，只需在比较相同元素时返回即可。

if a == b then
  return
end

在内部Lua的排序算法是Hoare分区方案的快速排序。分区时，枢轴值会从每一侧逐一比较每个元素，直到找到值相同或相反的元素，因此有机会比较相同的元素。