Ruby 中插入排序与二路插入排序的代码实现示例

在 Ruby 编程中，排序算法是非常重要的一部分。插入排序和二路插入排序是两种常见的排序算法，它们在不同的场景下具有不同的性能和应用。下面我们将详细介绍这两种排序算法在 Ruby 中的代码实现。

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。

以下是 Ruby 中插入排序的代码实现：

def insertion_sort(arr)
  n = arr.length

  (1..n - 1).each do |i|
    key = arr[i]
    j = i - 1

    while j >= 0 && arr[j] > key
      arr[j + 1] = arr[j]
      j -= 1
    end

    arr[j + 1] = key
  end

  arr
end

二路插入排序（Two-way Insertion Sort）是对插入排序的一种改进。它在插入元素时，不是从一端开始，而是从有序序列的两端同时进行比较和插入，从而提高了排序的效率。

以下是 Ruby 中二路插入排序的代码实现：

class TwoWayInsertionSort
  def sort(arr)
    first = nil
    last = nil

    arr.each do |item|
      if first.nil?
        first = Node.new(item)
        last = first
      else
        if item <= first.value
          new_node = Node.new(item)
          new_node.next = first
          first.prev = new_node
          first = new_node
        elsif item >= last.value
          new_node = Node.new(item)
          last.next = new_node
          new_node.prev = last
          last = new_node
        else
          current = first
          while current && item > current.value
            current = current.next
          end

          new_node = Node.new(item)
          new_node.prev = current.prev
          new_node.next = current
          current.prev.next = new_node
          current.prev = new_node
        end
      end
    end

    sorted_arr = []
    current = first
    while current
      sorted_arr << current.value
      current = current.next
    end

    sorted_arr
  end

  class Node
    attr_accessor :value, :prev, :next

    def initialize(value)
      @value = value
      @prev = nil
      @next = nil
    end
  end
end

通过以上代码实现，我们可以在 Ruby 中有效地使用插入排序和二路插入排序来对数组进行排序。在实际应用中，根据数据的特点和性能要求，选择合适的排序算法能够提高程序的运行效率。

无论是插入排序还是二路插入排序，它们都为我们在 Ruby 编程中处理数据排序问题提供了有效的工具和方法。熟练掌握这些算法的实现原理和代码编写，将有助于我们更好地应对各种排序需求。