Ruby实现插入排序算法及进阶的二路插入排序代码示例
基础将一个记录插入到一个已经排序好的表中，以得到一个记录增一的有序表。并且最关键的一点就是它把比当前元素大的记录都往后移动，用以空出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
def insertSort(tarray)
i=1
while(i < tarray.size) do
if tarray < tarray
j=i-1
x=tarray
#puts x.class
#puts tarray.class
tarray=tarray#先与左侧第一个比自己大的交换位置
while(x< tarray.to_i) do#寻找到一个比自己小的，并放在其后
tarray=tarray
#puts tarray.class
j=j-1
end
tarray=x
end
i=i+1
end
end
a=
insertSort(a)
print a
>Exit code: 0
刚开始写代码时，在x< tarray处没有加to_i方法，出现了如下错误：
final.rb:10:in `<': comparison of Fixnum with nil failed (ArgumentError)
一开始我很困惑，便在输出了x.class,tarray.class,然而这两的输出都是Fixnum。后来发现，Ruby的Array类和其他的不太一样,Ruby中允许一个Array对象中存储不同类型的元素，当a的一个元素赋值给x后，无法确定与x比较的a是否是Fixnum类型，所以报错，这只是我自己的理解。
进阶
2路插入排序基于折半插入排序：
def two_way_sort data
first,final = 0,0
temp = []
temp = data
result = []
len = data.length
for i in 1..(len-1)
if data>=temp
final +=1
temp = data
elsif data<= temp
first = (first -1 + len)%len
temp = data
else
if data<temp
low = first
high = len -1
while low <=high do
m = (low + high)>>1
if data>temp
low = m + 1
else
high = m -1
end
end
j = first - 1
first -=1
while j < high do
temp = temp
j +=1
end
temp = data
else
low =0
high = final
while low <=high do
m =(low + high)>>1
if data>=temp
low = m + 1
else
high = m - 1
end
end
j = final + 1
final +=1
while j > low do
temp = temp
j -=1
end
temp = data
end
end
p temp
end
i = 0
for j in first..(len - 1)
result = temp
i +=1
end
for j in 0..final
result = temp
i +=1
end
return result
end
data = .shuffle
p data
result = two_way_sort data
p result
页:
[1]