Ruby插入排序算法实现与二路插入排序代码示例

时间：2026-08-18 | 作者：星际追番人 | 阅读：0

插入排序可以说是排序算法里最直观的一种思路。它很像我们打牌时整理手牌：每次摸到一张新牌，就把它插入到已经排好序的位置里，最后整副手牌都会变得有序。

放到计算机里，这个思路同样很简单：把一个新记录插入到一个已经排序好的序列中，得到一个记录数加一的新有序表。

它的关键操作是，先把比当前元素大的记录依次后移，为新元素腾出位置。完成 n-1 趟这样的插入后，整个序列就排好了。

基础版插入排序

下面是一个 Ruby 实现的基础版插入排序代码。

写法非常直白：外层循环从第二个元素开始，逐个向后遍历。每次如果发现当前元素比前一个元素还小，就先把它取出来，再向前寻找合适的位置。

在寻找过程中，所有比它大的元素都会逐个后移，最后再把当前元素放进去。

def insertSort(tarray)
  i=1
  while(i < tarray.size) do
   if tarray[i] < tarray[i-1]
     j=i-1
     x=tarray[i]
     tarray[i]=tarray[i-1]#先与左侧第一个比自己大的交换位置
     while(x< tarray[j].to_i) do#寻找到一个比自己小的，并放在其后
      tarray[j+1]=tarray[j]
      j=j-1
     end
     tarray[j+1]=x
   end
   i=i+1
  end
end

a=[5,2,6,4,7,9,8]
insertSort(a)
print a

运行结果是：

[2, 4, 5, 6, 7, 8, 9]>Exit code: 0

一个常见报错

不过，初学者在写这段代码时，很容易踩到一个坑。

上面的循环条件里，一开始我用了 x < tarray[j]，没有加 .to_i，结果报了下面这个错：

final.rb:10:in `<': comparison of Fixnum with nil failed (ArgumentError)

当时我也有点疑惑，于是把 x 和 tarray[j] 的 class 都输出看了一下，发现两个都是 Fixnum。

但后来才意识到，问题并不在表面类型判断，而在于比较发生时，tarray[j] 可能已经是 nil 了。

Ruby 的 Array 和静态类型语言不一样。它允许同一个数组里存放不同类型的元素。当我们把数组中的某个元素赋值给 x 之后，紧接着参与比较的 tarray[j] 可能因为 j 越下界而变成 nil。

而 Ruby 不允许 Fixnum 和 nil 直接比较大小，所以就会抛出异常。

这是一个很典型的 Ruby 新手陷阱。理解这一点后，后面写循环条件时就需要更加留意边界问题。

进阶版：二路插入排序

基础版插入排序说完了，接下来看看进阶版——二路插入排序。

二路插入排序可以看作是折半插入排序的一种变体。它不再只是在一个线性表里反复移动元素，而是额外申请一个临时数组，并利用“循环队列”的思想来减少移动次数。

基本思路

先把第一个元素放到临时数组的中间，或者某个起始位置。
维护两个指针 first 和 final。
first 指向当前有序序列中最小元素的位置。
final 指向当前有序序列中最大元素的位置。
后续元素进入时，根据它和两端元素的大小关系，决定插入方式。

插入方式

如果元素较大，就从右侧直接追加。
如果元素较小，就从左侧“绕”过去插入。
如果元素位于中间区间，就使用折半查找找到合适位置后再插入。

下面是 Ruby 的实现代码，注释不多，但逻辑比较清晰：

def two_way_sort data
 first,final = 0,0
 temp = []
 temp[0] = data[0]
 result = []
 len = data.length

 for i in 1..(len-1)
  if data[i]>=temp[final]
   final +=1
   temp[final] = data[i]
  elsif data[i]<= temp[first]
   first = (first -1 + len)%len
   temp[first] = data[i]
  else
   if data[i]>1
     if data[i]>temp[m]
      low = m + 1
     else
      high = m -1
     end
    end
    
    j = first - 1
    first -=1
    while j < high do
     temp[j] = temp[j+1]
     j +=1
    end
 
    temp[high] = data[i]
   else
    low =0
    high = final

    while low <=high do
     m =(low + high)>>1

     if data[i]>=temp[m]
      low = m + 1
     else
      high = m - 1
     end
    end

    j = final + 1
    final +=1

    while j > low do
     temp[j] = temp[j-1]
     j -=1
    end 

    temp[low] = data[i]
   end
  end 
  p temp 
 end

 i = 0
 for j in first..(len - 1)
  result[i] = temp[j]
  i +=1
 end

 for j in 0..final
  result[i] = temp[j]
  i +=1
 end

 return result
end


data = [4,1,5,6,7,2,9,3,8].shuffle

p data

result = two_way_sort data

p result