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

[!--infotagslink--]

相关文章

  • antdesign-vue结合sortablejs实现两个table相互拖拽排序功能

    这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09
  • C# 参数按照ASCII码从小到大排序(字典序)

    这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
  • Ruby on Rails实现最基本的用户注册和登录功能的教程

    这里我们主要以has_secure_password的用户密码验证功能为中心,来讲解Ruby on Rails实现最基本的用户注册和登录功能的教程,需要的朋友可以参考下...2020-06-30
  • js实现列表按字母排序

    这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
  • C#实现排序的代码详解

    在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
  • js实现数组冒泡排序、快速排序原理

    这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
  • Ruby实现二分搜索(二分查找)算法的简单示例

    二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例:...2020-06-30
  • 图文详解Heap Sort堆排序算法及JavaScript的代码实现

    这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05
  • c# n个数排序实现代码

    c# n个数排序实现代...2020-06-25
  • 分享javascript实现的冒泡排序代码并优化

    本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
  • Ruby 字符串处理

    Ruby将字符串像数字一样处理.我们用单引号('...')或双引号("...")将它们括起来. ruby> "abc" "abc" ruby> 'abc' "abc" 单引号和双引号在某些情况下有不同的...2020-06-30
  • C#使用linq对数组进行筛选排序的方法

    这篇文章主要介绍了C#使用linq对数组进行筛选排序的方法,实例分析了C#实用linq扩展进行数组排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
  • JS实现的随机排序功能算法示例

    这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
  • Ruby on Rails中Rack中间件的基础学习教程

    Rack是一个连接Ruby程序与服务器程序之间的中间件,甚至可以说Rails也是在Rack的基础上建立起来的,这里我们就来为大家带来Ruby on Rails中Rack中间件的基础学习教程...2020-06-30
  • C#实现冒泡排序算法的代码示例

    冒泡排序即是对数组每次轮循出最大数或最小数放在队尾,这里我们来看一下C#实现冒泡排序算法的代码示例,需要的朋友可以参考下...2020-06-25
  • 实例讲解Ruby中的钩子方法及对方法调用添加钩子

    钩子方法即是在普通的方法上添加"钩子",使特定事件发生时可以被调用,下面就来以实例讲解Ruby中的钩子方法及对方法调用添加钩子...2020-06-30
  • 利用JavaScript对中文(汉字)进行排序实例详解

    排序是我们在日常开发中经常遇到的一个功能,下面这篇文章主要给大家介绍了利用JavaScript对中文(汉字)进行排序的相关资料,文中通过示例代码介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面跟着小编一起来看看吧。...2017-06-24
  • C++ STL关联式容器自定义排序规则的2种方法

    这篇文章主要介绍了C++ STL关联式容器自定义排序规则的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-04
  • JavaScript数值数组排序示例分享

    但是,我们在使用中就会发现问题,这里的数组排序方法并不是按照我们想像中的数字大小来排序的,而是按照字符串测试结果改变原先的数据。这并不是我们想要的。那么如何才可以得到我们想要的按照我们思维中的数字大小来排序...2014-05-31
  • C++ 字符串去重排序实例代码

    这篇文章主要介绍了C++ 字符串去重排序实例代码的相关资料,需要的朋友可以参考下...2020-04-25