Ruby实现插入排序算法及进阶的二路插入排序代码示例
基础
将一个记录插入到一个已经排序好的表中，以得到一个记录增一的有序表。并且最关键的一点就是它把比当前元素大的记录都往后移动，用以空出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
definsertSort(tarray) i=1 while(i<tarray.size)do iftarray[i]<tarray[i-1] j=i-1 x=tarray[i] #putsx.class #putstarray[i].class tarray[i]=tarray[i-1]#先与左侧第一个比自己大的交换位置 while(x<tarray[j].to_i)do#寻找到一个比自己小的，并放在其后 tarray[j+1]=tarray[j] #putstarray[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) printa
[2,4,5,6,7,8,9]>Exitcode:0
刚开始写代码时，在x<tarray[j]处没有加to_i方法，出现了如下错误：
final.rb:10:in`<':comparisonofFixnumwithnilfailed(ArgumentError)
一开始我很困惑，便在输出了x.class,tarray[j].class,然而这两的输出都是Fixnum。后来发现，Ruby的Array类和其他的不太一样,Ruby中允许一个Array对象中存储不同类型的元素，当a的一个元素赋值给x后，无法确定与x比较的a[i]是否是Fixnum类型，所以报错，这只是我自己的理解。
进阶
2路插入排序基于折半插入排序：
deftwo_way_sortdata first,final=0,0 temp=[] temp[0]=data[0] result=[] len=data.length foriin1..(len-1) ifdata[i]>=temp[final] final+=1 temp[final]=data[i] elsifdata[i]<=temp[first] first=(first-1+len)%len temp[first]=data[i] else ifdata[i]<temp[0] low=first high=len-1 whilelow<=highdo m=(low+high)>>1 ifdata[i]>temp[m] low=m+1 else high=m-1 end end j=first-1 first-=1 whilej<highdo temp[j]=temp[j+1] j+=1 end temp[high]=data[i] else low=0 high=final whilelow<=highdo m=(low+high)>>1 ifdata[i]>=temp[m] low=m+1 else high=m-1 end end j=final+1 final+=1 whilej>lowdo temp[j]=temp[j-1] j-=1 end temp[low]=data[i] end end ptemp end i=0 forjinfirst..(len-1) result[i]=temp[j] i+=1 end forjin0..final result[i]=temp[j] i+=1 end returnresult end data=[4,1,5,6,7,2,9,3,8].shuffle pdata result=two_way_sortdata presult