如何在Ruby中对字母数字数组进行排序

Question

如何在Ruby中按字母数字排序数组数据？

假设我的数组是a = [test_0_1, test_0_2, test_0_3, test_0_4, test_0_5, test_0_6, test_0_7, test_0_8, test_0_9, test_1_0, test_1_1, test_1_2, test_1_3, test_1_4, test_1_5, test_1_6, test_1_7, test_1_8, test_1_9, test_1_10, test_1_11, test_1_12, test_1_13, test_1_14, ...........test_1_121...............]

我希望输出结果为：

.
.
.
test_1_121
.
.
.
test_1_14
test_1_13
test_1_12
test_1_11
test_1_10
test_1_9
test_1_8
test_1_7
test_1_6
test_1_5
test_1_4
test_1_3
test_1_2
test_1_1
test_0_10
test_0_9
test_0_8
test_0_7
test_0_6
test_0_5
test_0_4
test_0_3
test_0_2
test_0_1

- user682932

---

因为这里所需的排序不是简单比较两个值，所以你需要使用 sort_by。操作字符串或深入对象所引起的开销可能会导致 sort 效率低下。 - the Tin Man

Answer 1

一种通用算法，用于对包含任意位置的非填充序列号的字符串进行排序。

padding = 4
list.sort{|a,b|
  a,b = [a,b].map{|s| s.gsub(/\d+/){|m| "0"*(padding - m.size) + m } }
  a<=>b
}

其中padding是您希望在比较时数字具有的字段长度。如果字符串中包含的数字小于“填充”数字的数量，则会进行零填充，以便在比较之前得出预期排序顺序。

要得到用户682932要求的结果，只需在排序块后添加.reverse即可将自然排序（升序）翻转为降序。

通过对字符串进行预循环，您当然可以动态查找字符串列表中最大数字的位数，而不是硬编码一些任意的填充长度，但这会需要更多的处理（速度更慢）和更多的代码。例如：

padding = list.reduce(0){|max,s| 
  x = s.scan(/\d+/).map{|m|m.size}.max
  (x||0) > max ? x : max
}

- Jojje

---

我喜欢填充的想法，但在两种情况下它不起作用：1.数字序列比填充更长。2.像“1.1.1.1…”这样的长字符串，如果填充太大，其大小会被乘以很多倍，无法适应内存。 - Cœur

Answer 2

如果你只是按照字符串排序，那么在'test_2'和'test_10'之间就无法得到正确的排序。因此，请使用以下方式进行排序:

sort_by{|s| s.scan(/\d+/).map{|s| s.to_i}}.reverse

- sawa

Answer 3

排序算法的处理时间可以有很大差异。对排序算法进行基准测试可以快速找出最快的方法：

#!/usr/bin/env ruby

ary = %w[
    test_0_1  test_0_2   test_0_3 test_0_4 test_0_5  test_0_6  test_0_7
    test_0_8  test_0_9   test_1_0 test_1_1 test_1_2  test_1_3  test_1_4  test_1_5
    test_1_6  test_1_7   test_1_8 test_1_9 test_1_10 test_1_11 test_1_12 test_1_13
    test_1_14 test_1_121
]

require 'ap'
ap ary.sort_by { |v| a,b,c = v.split(/_+/); [a, b.to_i, c.to_i] }.reverse

并输出：

>> [
>>     [ 0] "test_1_121",
>>     [ 1] "test_1_14",
>>     [ 2] "test_1_13",
>>     [ 3] "test_1_12",
>>     [ 4] "test_1_11",
>>     [ 5] "test_1_10",
>>     [ 6] "test_1_9",
>>     [ 7] "test_1_8",
>>     [ 8] "test_1_7",
>>     [ 9] "test_1_6",
>>     [10] "test_1_5",
>>     [11] "test_1_4",
>>     [12] "test_1_3",
>>     [13] "test_1_2",
>>     [14] "test_1_1",
>>     [15] "test_1_0",
>>     [16] "test_0_9",
>>     [17] "test_0_8",
>>     [18] "test_0_7",
>>     [19] "test_0_6",
>>     [20] "test_0_5",
>>     [21] "test_0_4",
>>     [22] "test_0_3",
>>     [23] "test_0_2",
>>     [24] "test_0_1"
>> ]

测试算法的速度表明：

require 'benchmark'

n = 50_000
Benchmark.bm(8) do |x|
  x.report('sort1') { n.times { ary.sort { |a,b| b <=> a }         } }
  x.report('sort2') { n.times { ary.sort { |a,b| a <=> b }.reverse } }
  x.report('sort3') { n.times { ary.sort { |a,b|
                                  ap = a.split('_')
                                  a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
                                  bp = b.split('_')
                                  b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
                                  b <=> a
                                } } }

  x.report('sort_by1') { n.times { ary.sort_by { |s| s                                               }         } }
  x.report('sort_by2') { n.times { ary.sort_by { |s| s                                               }.reverse } }
  x.report('sort_by3') { n.times { ary.sort_by { |s| s.scan(/\d+/).map{ |s| s.to_i }                 }.reverse } }
  x.report('sort_by4') { n.times { ary.sort_by { |v| a = v.split(/_+/); [a[0], a[1].to_i, a[2].to_i] }.reverse } }
  x.report('sort_by5') { n.times { ary.sort_by { |v| a,b,c = v.split(/_+/); [a, b.to_i, c.to_i]      }.reverse } }
end


>>               user     system      total        real
>> sort1     0.900000   0.010000   0.910000 (  0.919115)
>> sort2     0.880000   0.000000   0.880000 (  0.893920)
>> sort3    43.840000   0.070000  43.910000 ( 45.970928)
>> sort_by1  0.870000   0.010000   0.880000 (  1.077598)
>> sort_by2  0.820000   0.000000   0.820000 (  0.858309)
>> sort_by3  7.060000   0.020000   7.080000 (  7.623183)
>> sort_by4  6.800000   0.000000   6.800000 (  6.827472)
>> sort_by5  6.730000   0.000000   6.730000 (  6.762403)
>> 

Sort1、sort2、sort_by1和sort_by2有助于建立sort、sort_by以及这两者与reverse的基线。

Sort3和sort_by3是本页上的另外两个答案。Sort_by4和sort_by5则是我想到的两种方法，其中sort_by5是我在几分钟的摆弄后想出的最快方法。

这说明算法中的小差异可能会对最终输出产生影响。如果有更多的迭代或需要排序的数组更大，那么差异将更加明显。

- the Tin Man

Answer 4

您可以将一个块传递给sort函数以自定义排序。在您的情况下，您会遇到一个问题，因为您的数字没有零填充，所以此方法会对数字部分进行零填充，然后对它们进行排序，从而得到您想要的排序顺序。

a.sort { |a,b|
  ap = a.split('_')
  a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
  bp = b.split('_')
  b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
  b <=> a
}

- Chris Cherry

Answer 5

与@ctcherry的答案类似，但更快：

a.sort_by {|s| "%s%05i%05i" % s.split('_') }.reverse

编辑：我的测试：

require 'benchmark'
ary = []
100_000.times { ary << "test_#{rand(1000)}_#{rand(1000)}" }
ary.uniq!; puts "Size: #{ary.size}"

Benchmark.bm(5) do |x|
  x.report("sort1") do
    ary.sort_by {|e| "%s%05i%05i" % e.split('_') }.reverse
  end
  x.report("sort2") do
    ary.sort { |a,b|
      ap = a.split('_')
      a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
      bp = b.split('_')
      b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
      b <=> a
    } 
  end
  x.report("sort3") do
    ary.sort_by { |v| a, b, c = v.split(/_+/); [a, b.to_i, c.to_i] }.reverse
  end
end

输出：

Size: 95166

           user     system      total        real
sort1  3.401000   0.000000   3.401000 (  3.394194)
sort2 94.880000   0.624000  95.504000 ( 95.722475)
sort3  3.494000   0.000000   3.494000 (  3.501201)

- Guilherme Bernal

---

为什么不展示你的测试？当解释某项操作更快时，基准测试结果非常有用。 - the Tin Man

Answer 6

我查看了Unix的sort函数的维基百科页面，其中GNU版本具有一个-V标志，可以通用地对“版本字符串”进行排序（我认为这意味着数字和非数字的混合，在这种情况下，您希望数字部分按数字顺序排序，而非数字部分按字典顺序排序）。

该文章指出：

GNU实现具有-V --version-sort选项，它是文本中(版本)数字的自然排序。要比较的两个文本字符串被分成字母块和数字块。字母块按字母数字顺序比较，数字块按数字顺序比较（即跳过前导零，更多的数字意味着更大，否则最左边不同的数字确定结果）。块从左到右比较，并且在该循环中第一个非相等块决定哪个文本更大。这适用于IP地址、Debian软件包版本字符串和类似任务，其中可变长度的数字嵌入在字符串中。 sawa的解决方案有些类似，但不会按非数字部分排序。

因此，在Coeur和sawa之间发布一种解决方案似乎很有用，它的工作方式类似于GNU的sort -V。

a.sort_by do |r|
  # Split the field into array of [<string>, nil] or [nil, <number>] pairs
  r.to_s.scan(/(\D+)|(\d+)/).map do |m|
    s,n = m
    n ? n.to_i : s.to_s # Convert number strings to integers
  end.to_a
end

在我的情况下，我想按字段对一个TSV文件进行排序，像这样，因此作为额外的奖励，这里也有这种情况的脚本：

require 'csv'

# Sorts a tab-delimited file input on STDIN, sortin

opts = {
  headers:true,
  col_sep: "\t",
  liberal_parsing: true,
}

table = CSV.new($stdin, **opts)


# Emulate unix's sort -V: split each field into an array of string or
# numeric values, and sort by those in turn. So for example, A10
# sorts above A100.
sorted_ary = table.sort_by do |r|
  r.fields.map do |f|
    # Split the field into array of [<string>, nil] or [nil, <number>] values
    f.to_s.scan(/(\D+)|(\d+)/).map do |m|
      s,n = m
      n ? n.to_i : s.to_s # Convert number strings to integers
    end.to_a
  end
end

puts CSV::Table.new(sorted_ary).to_csv(**opts)

（旁注：另一个解决方案在这里使用Gem::Version进行排序，但这似乎只适用于格式良好的Gem版本字符串。）

- wu-lee

---

需要注意的是，TSV有时与逗号分隔的CSV文件略有不同，其分隔符为\t：https://dev59.com/Fm855IYBdhLWcg3wVist - wu-lee

Answer 7

这里提供了一种更通用的在Ruby中执行自然十进制排序的方法。以下内容受到了我用于“像Xcode一样”排序的代码的启发，该代码来自https://github.com/CocoaPods/Xcodeproj/blob/ca7b41deb38f43c14d066f62a55edcd53876cd07/lib/xcodeproj/project/object/helpers/sort_helper.rb，它本身受到https://rosettacode.org/wiki/Natural_sorting#Ruby的启发。

即使我们希望在自然十进制排序中将“10”放在“2”之后，但还有其他方面需要考虑，因为可能存在多种可选的行为。

• 我们如何对待类似于“001”/“01”的相等情况：保留原始数组顺序还是有后备逻辑？（下面，选择在第一次排序时出现相等情况时进行第二遍严格排序）
• 我们是否忽略连续的空格进行排序，或者每个空格字符都计数？（下面，选择在第一次排序时忽略连续的空格，并在相等情况时进行严格比较）
• 其他特殊字符也是同样的问题。（下面，选择让任何非空格和非数字的字符单独计数）
• 我们是否忽略大小写；“a”在“A”之前还是之后？（下面，选择在第一次排序时忽略大小写，在相等情况时将“a”放在“A”之前）

考虑到这些因素：

• 这意味着我们几乎肯定应该使用scan而不是split，因为我们将有潜在的三种子字符串进行比较（数字、空格、其余所有内容）。
• 这意味着我们几乎肯定要使用Comparable类和def <=>(other)方法，因为不能简单地将每个子字符串映射到另一个具有两个不同行为的东西，具体取决于上下文（第一遍和相等性检查）。

这导致了一个有点冗长的实现，但它对于边缘情况非常有效：

  # Wrapper for a string that performs a natural decimal sort (alphanumeric).
  # @example
  #   arrayOfFilenames.sort_by { |s| NaturalSortString.new(s) }
  class NaturalSortString
    include Comparable
    attr_reader :str_fallback, :ints_and_strings, :ints_and_strings_fallback, :str_pattern

    def initialize(str)
      # fallback pass: case is inverted
      @str_fallback = str.swapcase
      # first pass: digits are used as integers, spaces are compacted, case is ignored
      @ints_and_strings = str.scan(/\d+|\s+|[^\d\s]+/).map do |s|
        case s
        when /\d/ then Integer(s, 10)
        when /\s/ then ' '
        else s.downcase
        end
      end
      # second pass: digits are inverted, case is inverted
      @ints_and_strings_fallback = @str_fallback.scan(/\d+|\D+/).map do |s|
        case s
        when /\d/ then Integer(s.reverse, 10)
        else s
        end
      end
      # comparing patterns
      @str_pattern = @ints_and_strings.map { |el| el.is_a?(Integer) ? :i : :s }.join
    end

    def <=>(other)
      if str_pattern.start_with?(other.str_pattern) || other.str_pattern.start_with?(str_pattern)
        compare = ints_and_strings <=> other.ints_and_strings
        if compare != 0
          # we sort naturally (literal ints, spaces simplified, case ignored)
          compare
        else
          # natural equality, we use the fallback sort (int reversed, case swapped)
          ints_and_strings_fallback <=> other.ints_and_strings_fallback
        end
      else
        # type mismatch, we sort alphabetically (case swapped)
        str_fallback <=> other.str_fallback
      end
    end
  end

使用方法

示例 1：

arrayOfFilenames.sort_by { |s| NaturalSortString.new(s) }

示例2：

arrayOfFilenames.sort! do |x, y|
  NaturalSortString.new(x) <=> NaturalSortString.new(y)
end

你可以在https://github.com/CocoaPods/Xcodeproj/blob/ca7b41deb38f43c14d066f62a55edcd53876cd07/spec/project/object/helpers/sort_helper_spec.rb找到我的测试用例，我使用了以下参考进行排序： [ ' a', ' a', '0.1.1', '0.1.01', '0.1.2', '0.1.10', '1', '01', '1a', '2', '2 a', '10', 'a', 'A', 'a ', 'a 2', 'a1', 'A1B001', 'A01B1', ]

当然，现在可以随意定制自己的排序逻辑。

- Cœur

---

这个方法能否应用于Dir.entries(src).sort.each do |item|，其中文件名看起来像1886–7 Los Angeles City Directory. Bynon. p221. Suzzalo.jpg，我想自然排序数字在p之后，它们将高达9999，并且可能包括其他字符，例如pi，但除了数字以外的任何内容都可以忽略，但仍需要包含（最终在末尾或开头）？ 我可以想象抓取数组中的所有文件名，然后从那里继续，但我不擅长Ruby，因此更直接的方法将是首选。并且使用所有Ruby魔法，也许。 - Greg

Answer 8

从外观上看，您想要使用排序函数和/或反转函数。

ruby-1.9.2-p136 :009 > a = ["abc_1", "abc_11", "abc_2", "abc_3", "abc_22"]
 => ["abc_1", "abc_11", "abc_2", "abc_3", "abc_22"] 

ruby-1.9.2-p136 :010 > a.sort
 => ["abc_1", "abc_11", "abc_2", "abc_22", "abc_3"] 
ruby-1.9.2-p136 :011 > a.sort.reverse
 => ["abc_3", "abc_22", "abc_2", "abc_11", "abc_1"] 

- Mike Lewis

---

尝试以下代码：a = [test_0_1，test_0_2，test_0_3，test_0_4，test_0_5，test_0_6，test_0_7，test_0_8，test_0_9，test_1_0，test_1_1，test_1_2，test_1_3，test_1_4，test_1_5，test_1_6，test_1_7，test_1_8，test_1_9，test_1_10，test_1_11，test_1_12，test_1_13，test_1_14，……test_1_121……] 其中有两个下划线。它不能工作。 - user682932

Answer 9

好的，根据你的输出，似乎你只是想要将其反转，因此可以使用reverse()

a.reverse

- kurumi