检查数组是否已经排序?

我知道如何按顺序放置一个数组,但在这种情况下,我只是想知道它是否有序。 我想,一串字符串将是最简单的,并且在该方面的答案是值得赞赏的,但是包括基于某些任意参数检查顺序的能力的答案是最佳的。

这是一个示例数据集。 名称:

[["a", 3],["b",53],["c",2]] 

元素本身是包含多个元素的数组,其中第一个是字符串。 我想看看这些元素是否按字母顺序排列。

它看起来像一个通用的抽象,让我们打开Enumerable

 module Enumerable def sorted? each_cons(2).all? { |a, b| (a <=> b) <= 0 } end end [["a", 3], ["b", 53],["c", 2]].sorted? #=> true 

请注意,我们必须写(a <=> b) <= 0而不是a <= b因为有些类支持<=>但不支持比较器运算符(即Array),因为它们不包含Comparable模块。

您还说过您希望能够“根据某些任意参数检查订单”:

 module Enumerable def sorted_by? each_cons(2).all? { |a, b| ((yield a) <=> (yield b)) <= 0 } end end [["a", 3], ["b", 1], ["c", 2]].sorted_by? { |k, v| v } #=> false 

使用lazy enumerables(Ruby> = 2.1),我们可以重用Enumerable#sorted?

 module Enumerable def sorted_by?(&block) lazy.map(&block).sorted? end end 

你可以两个比较它们:

 [["a", 3],["b",53],["c",2]].each_cons(2).all?{|p, n| (p <=> n) != 1} # => true 

reduce可以将每个元素与之前的元素进行比较,并在发现一个元素无序时停止:

 array.reduce{|prev,l| break unless l[0] >= prev[0]; l} 

如果事实certificate数组没有排序,你的下一个动作总是要对它进行排序吗? 对于该用例(虽然当然取决于数组已经排序的次数),您可能不想检查它是否已排序,而只是选择始终对数组进行排序。 对已经排序的数组进行排序对于许多算法来说是非常有效的,并且只是检查数组是否已经排序并没有那么多工作,使得检查+排序比简单的排序更有效。

 def ascending? (array) yes = true array.reduce { |l, r| break unless yes &= (l[0] <= r[0]); l } yes end def descending? (array) yes = true array.reduce { |l, r| break unless yes &= (l[0] >= r[0]); l } yes end 

迭代对象并确保每个后续元素> =当前元素(或前一个<=,显然是当前元素)。

为了有效地工作,您需要在插入期间进行排序。 如果您正在处理唯一项目,则还可以选择SortedSet 。

为了澄清,如果我们修补数组以允许排序插入,那么我们可以将数组保持在排序状态:

 class Array def add_sorted(o) size = self.size if size == 0 self << o elsif self.last < o self << o elsif self.first > o self.insert(0, o) else # This portion can be improved by using a binary search instead of linear self.each_with_index {|n, i| if n > o; self.insert(i, o); break; end} end end end a = [] 12.times{a.add_sorted(Random.rand(10))} pa # => [1, 1, 2, 2, 3, 4, 5, 5, 5, 5, 7] 

或使用内置排序:

 class Array def add_sorted2(o) self << o self.sort end end 

或者,如果您正在处理独特的项目:

 require "set" b = SortedSet.new 12.times{b << Random.rand(10)} pb # => # 

这些都太难了。 您不必排序,但可以使用 sort来检查。 下面的乱序数组用于演示目的。

 arr = [["b",3],["a",53],["c",2]] arr.sort == arr # => false p arr.sort # => [["a",53],["b",3],["c",2]]