Ruby实现插入排序算法及进阶的二路插入排序代码示例

    基础
    将一个记录插入到一个已经排序好的表中,以得到一个记录增一的有序表。并且最关键的一点就是它把比当前元素大的记录都往后移动,用以空出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。

    
    def insertSort(tarray)
      i=1
      while(i < tarray.size) do
       if tarray[i] < tarray[i-1]
         j=i-1
         x=tarray[i]
       #puts x.class
       #puts tarray[i].class
         tarray[i]=tarray[i-1]#先与左侧第一个比自己大的交换位置
         while(x< tarray[j].to_i) do#寻找到一个比自己小的,并放在其后
          tarray[j+1]=tarray[j]
          #puts tarray[j].class
          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.class,tarray[j].class,然而这两的输出都是Fixnum。后来发现,Ruby的Array类和其他的不太一样,Ruby中允许一个Array对象中存储不同类型的元素,当a的一个元素赋值给x后,无法确定与x比较的a[i]是否是Fixnum类型,所以报错,这只是我自己的理解。

    进阶
    2路插入排序基于折半插入排序:

    
    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]<temp[0]
        low = first
        high = len -1
       
        while low <=high do
         m = (low + high)>>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