检查数组是否已经排序?
我知道如何按顺序放置一个数组,但在这种情况下,我只是想知道它是否有序。 我想,一串字符串将是最简单的,并且在该方面的答案是值得赞赏的,但是包括基于某些任意参数检查顺序的能力的答案是最佳的。
这是一个示例数据集。 名称:
[["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]]