Ruby實(shí)現(xiàn)插入排序算法及進(jìn)階的二路插入排序代碼示例
基礎(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
剛開(kāi)始寫(xiě)代碼時(shí)，在x< tarray[j]處沒(méi)有加to_i方法，出現(xiàn)了如下錯(cuò)誤：
final.rb:10:in `<': comparison of Fixnum with nil failed (ArgumentError)
一開(kāi)始我很困惑，便在輸出了x.class,tarray[j].class,然而這兩的輸出都是Fixnum。后來(lái)發(fā)現(xiàn)，Ruby的Array類和其他的不太一樣,Ruby中允許一個(gè)Array對(duì)象中存儲(chǔ)不同類型的元素，當(dāng)a的一個(gè)元素賦值給x后，無(wú)法確定與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
版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信