2 
# sort.rb
class Array
  def insertion
    (1..self.count).each do |i|
      (i..0).each do |j|
        first = j - 1
        second = j
        if self[second] > self[first]
          swap(second, first)
        end
      end
    end
    self
  end

  def mergesort
    return self if self.size <= 1
    mid = self.size / 2
    left = self[0, mid]
    right = self[mid, self.size-mid]
    merge_array(left.mergesort, right.mergesort)
  end

  # helpers

  def merge_array(left, right)
    sorted = []
    until left.empty? or right.empty?
      if left.first <= right.first
        sorted << left.shift
      else
        sorted << right.shift
      end
    end
    sorted.concat(left).concat(right)
  end

  def swap(previous, current)
    copy = self[previous]
    self[previous] = self[current]
    self[current] = copy
  end
end

我的 rspec 文件：

require './sort'

unsorted = 5000.downto(1).to_a.shuffle

describe Array, "#insertion" do
  it "sorts using insertion sort" do
    time = Time.now
    unsorted.insertion.should eq(unsorted.sort)
    puts "insertion"
    puts Time.now - time
  end
end

describe Array, "#merge" do
  it "sorts using merge sort" do
    time = Time.now
    unsorted.mergesort.should eq(unsorted.sort)
    puts "merge"
    puts Time.now - time
  end
end

我们知道插入排序应该比归并排序慢，因为插入排序的运行时间平均为 O(n^2)，而归并排序为 O(n*log(n))。但是，当我运行上面的测试代码时，合并比插入慢 10 倍以上。

插入
0.001294 秒

。合并
0.017322 秒

我的猜测是我使用了一些计算量大的方法，比如shiftand concat，但是相差 10 倍就太夸张了。

如何改进归并排序？

4

2 回答 2

8

这里有很多东西：

  1. 这不是插入排序，而是冒泡排序。
  2. (i..0).each什么都不做，因为范围不能以相反的顺序排列（您的规范没有通过）。改为使用downto。
  3. 逻辑本身就是错误的，如果您的最后一个索引位于字符串的开头，那么您想在第二个元素小于第一个元素时进行交换。
  4. 您的规范使用相同的数组，但是插入方法会改变数组，所以当它到达合并排序时，它已经被排序了。
  5. 没有很好的理由将这些放在 Array 上（除了它的新颖性之外），一般来说，猴子补丁是一种不好的做法（我会解释原因，但这有点超出了这个响应的范围）。
  6. 可以通过多次赋值来简化交换方法self[a], self[b] = self[b], self[a]。
  7. first, second, previous, ,的名字next都令人困惑。他们的名字暗示他们是元素，但实际上他们是索引，我会重命名为index1（也许first_index是，但这可能会变得冗长）。
  8. 为什么要在count和之间切换size？这很令人困惑，看起来就像您复制和粘贴了其他人的代码（事实上，其中一个函数会改变数组而另一个不会，一般来说，合并排序看起来像是由知道的人编写的他们在做什么，而“插入”排序没有）。
  9. 合并排序可能更慢，因为它会在不需要的地方创建大量数组（它没有副作用，但从性能的角度来看，最好只dup使用数组，然后根据 start 和结束索引。
  10. 这些测试不是很有用，因为它们只对一个数组进行排序。假设数组已经基本排序，那么冒泡排序必须执行的交换很少，所以它只是迭代数组多次就完成了。
  11. 这些调用之间可能会发生环境差异（优化、垃圾收集状态），最好使用 Benchmark 库。它bmbm试图最小化这些差异。
  12. 因为您在 timer 内运行测试unsorted.insertion.should eq(unsorted.sort)，所以您不仅在为排序计时，还在unsorted.sort为 Ruby 和 RSpec 断言计时。最好将排序包装在时序代码中，然后输出结果。
于 2013-03-08T02:05:56.733 回答
4

想法：

  • 尝试将您的测试大小增加到数十万，并在几个不同的数组上取平均值，因为与合并排序相比，插入排序在最好的情况下会非常快
  • 在合并中预先分配数组而不是动态构建数组，因为您应该知道大小
  • 从时间匹配中提取正确性（...应该）调用
于 2013-03-08T01:11:44.243 回答