基礎(chǔ)
將一個(gè)記錄插入到一個(gè)已經(jīng)排序好的表中，以得到一個(gè)記錄增一的有序表。并且最關(guān)鍵的一點(diǎn)就是它把比當(dāng)前元素大的記錄都往后移動(dòng)，用以空出“自己”該插入的位置。當(dāng)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]#先與左側(cè)第一個(gè)比自己大的交換位置
while(x tarray[j].to_i) do#尋找到一個(gè)比自己小的，并放在其后
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
剛開始寫代碼時(shí)，在x tarray[j]處沒有加to_i方法，出現(xiàn)了如下錯(cuò)誤：
final.rb:10:in `': comparison of Fixnum with nil failed (ArgumentError)
一開始我很困惑，便在輸出了x.class,tarray[j].class,然而這兩的輸出都是Fixnum。后來發(fā)現(xiàn)，Ruby的Array類和其他的不太一樣,Ruby中允許一個(gè)Array對(duì)象中存儲(chǔ)不同類型的元素，當(dāng)a的一個(gè)元素賦值給x后，無法確定與x比較的a[i]是否是Fixnum類型，所以報(bào)錯(cuò)，這只是我自己的理解。
進(jìn)階
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
標(biāo)簽：六安 河北 宜春 石嘴山 自貢 淄博 鄂州 松原
巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《Ruby實(shí)現(xiàn)插入排序算法及進(jìn)階的二路插入排序代碼示例》，本文關(guān)鍵詞 Ruby,實(shí)現(xiàn),插入,排序,算法,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。
