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
相关推荐
-
Ruby实现的各种排序算法
时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a) (a.size-2).downto(0) do |i| (0..i).each do |j| a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1] end end return a end Selection sort 复制代码 代码如下: def selection_sort(a) b =
-
Ruby一行代码实现的快速排序
复制代码 代码如下: def quick_sort(a) return a if a.size < 2 (x = a.pop) ? quick_sort(a.select{|i| i <=x }) + [x] + quick_sort(a.select{|i| i > x}) : [] end array = [72,6,57,88,60,42,83,73,42,48,85] p quick_sort(array) #=> [6, 42, 42, 48, 57, 60, 7
-
Ruby实现的合并排序算法
算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i
-
ruby实现的插入排序和冒泡排序算法
1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i| if seq[i] < seq[i-1] tmp = seq[i] j = i-1 while(j>=0 && tmp<seq[j]) do seq[j+1] = seq[j] j=j-1 end seq[j+1]=tmp endend seq.each {|num| puts
-
冒泡排序算法及Ruby版的简单实现
算法原理: 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 实现 假设有这样一个数组: [4, 1, 3, 2] 冒泡排序为从第一个数开始,吧这个数与后面的数比较,如果这个数比后面的大,就交换他们的位置. 比如,第一次比较4和1,发现4比1大,交换 -> [1, 4, 3,
-
Ruby实现的3种快速排序算法
刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul
-
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
-
插入排序算法之希尔排序+直接插入排序
希尔排序 在介绍希尔排序之前,先了解一下直接插入排序 一.直接插入排序 1. 单趟排序 x插入一个有序区间 这里end是指向数组最后一个元素 2. 直接插入排序 根据上面的单趟排序启发 end是数组的最后一个元素,end之后的元素都是待排序 一个关键的判断点,end和x比较大小 这里end < x 还需要再做改善 可以发现有两个循环,一个循环时end倒着遍历完之后,使得最开始的end结束的数组加入x后是一个有序数组,最后再返回这个新数组的最后一个元素所在位置 注意公共部分 end--: x =
-
详解直接插入排序算法与相关的Java版代码实现
直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们
-
Ruby使用C++扩展实例（含C++扩展代码示例）
早年写过用C++ + SWIG写Ruby插件的文,但实际中还是以原生C++写Ruby扩展,因为也相当简单.但长久没用还是会忘记,不得不翻以前的老代码回忆,写下这篇博文,若下次再忘记,也不至于去翻仓库. 建立 extconf.rb 复制代码 代码如下: require 'mkmf' $libs = '-lstdc++' create_makefile 'foo' 建立 foo.cc 复制代码 代码如下: #include <ruby.h> VALUE plus(VALUE self, VALUE
-
Java实现插入排序算法可视化的示例代码
参考文章 图解Java中插入排序算法的原理与实现 实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =
-
Python实现的插入排序算法原理与用法实例分析
本文实例讲述了Python实现的插入排序算法原理与用法.分享给大家供大家参考,具体如下: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 插
-
Python实现的直接插入排序算法示例
本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现 时间复杂度O(n**2) 空间复杂度O(1) 稳定 思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in
-
java实现插入排序算法
1.算法概念. 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 2.算法思想. 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. public static void insertSort(int[] array) { int len = array.length; for (int i = 1; i < len;
-
python插入排序算法实例分析
本文实例讲述了python插入排序算法.分享给大家供大家参考.具体如下: def insertsort(array): for removed_index in range(1, len(array)): removed_value = array[removed_index] insert_index = removed_index while insert_index > 0 and array[insert_index - 1] > removed_value: array[insert
-
浅谈插入排序算法在Python程序中的实现及简单改进
Python实现插入排序的一般范例为: #coding=cp936 #coding=cp936 #插入排序算法 def InsertionSort(A): for j in range(1,len(A)): key = A[j] i = j-1 #向前查找插入位置 while i>=0 and A[i]>key: A[i+1] = A[i] i = i-1 A[i+1] = key #初始化输入数据 A = [] input = raw_input('please input some num