Ruby实现插入排序算法及进阶的二路插入排序代码示例
更新时间:2020年6月30日 23:54 点击:2254
基础
将一个记录插入到一个已经排序好的表中,以得到一个记录增一的有序表。并且最关键的一点就是它把比当前元素大的记录都往后移动,用以空出“自己”该插入的位置。当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
相关文章
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
Ruby on Rails实现最基本的用户注册和登录功能的教程
这里我们主要以has_secure_password的用户密码验证功能为中心,来讲解Ruby on Rails实现最基本的用户注册和登录功能的教程,需要的朋友可以参考下...2020-06-30- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例:...2020-06-30
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- c# n个数排序实现代...2020-06-25
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
- Ruby将字符串像数字一样处理.我们用单引号('...')或双引号("...")将它们括起来. ruby> "abc" "abc" ruby> 'abc' "abc" 单引号和双引号在某些情况下有不同的...2020-06-30
- 这篇文章主要介绍了C#使用linq对数组进行筛选排序的方法,实例分析了C#实用linq扩展进行数组排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- Rack是一个连接Ruby程序与服务器程序之间的中间件,甚至可以说Rails也是在Rack的基础上建立起来的,这里我们就来为大家带来Ruby on Rails中Rack中间件的基础学习教程...2020-06-30
- 冒泡排序即是对数组每次轮循出最大数或最小数放在队尾,这里我们来看一下C#实现冒泡排序算法的代码示例,需要的朋友可以参考下...2020-06-25
- 钩子方法即是在普通的方法上添加"钩子",使特定事件发生时可以被调用,下面就来以实例讲解Ruby中的钩子方法及对方法调用添加钩子...2020-06-30
- 排序是我们在日常开发中经常遇到的一个功能,下面这篇文章主要给大家介绍了利用JavaScript对中文(汉字)进行排序的相关资料,文中通过示例代码介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面跟着小编一起来看看吧。...2017-06-24
- 这篇文章主要介绍了C++ STL关联式容器自定义排序规则的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-04
- 但是,我们在使用中就会发现问题,这里的数组排序方法并不是按照我们想像中的数字大小来排序的,而是按照字符串测试结果改变原先的数据。这并不是我们想要的。那么如何才可以得到我们想要的按照我们思维中的数字大小来排序...2014-05-31
- 这篇文章主要介绍了C++ 字符串去重排序实例代码的相关资料,需要的朋友可以参考下...2020-04-25