首页 » Ruby » Ruby插入排序的常规写法和递归写法

Ruby插入排序的常规写法和递归写法

原文 http://blog.csdn.net/o83290102o5/article/details/78819471

2017-12-19 02:01:04阅读(515)

用循环的常规写法

arr=[5,2,3,1,4]
#循环下表1~arr.length,注意初始时最左边因为只有一个值,所以可以看成左边数组0~1已经有序
1.upto arr.length-1 do |outIndex|
  #取值
  element=arr[outIndex]
  #生成子下标,数值为外部下标的左边一位(因为自己与自己比较没有意义)
  index=outIndex-1
  #下标从outIndex-1 循环到 0,每次将大于element的值往右拷贝一位,同时记录下标的当前位置
  while index>=0 and element<arr[index]
    arr[index+1]=arr[index]
    index-=1
  end
  #循环退出时的下标就正好是element最后对应的位置
  arr[index+1]=element
end
puts arr.to_s

递归式写法,这个也是算导上的一道题目。

arr=[5,2,3,1,4]
#递归式的写法这样看待问题
# 为了排序[1..n],每次排序[1..n-1],然后再将A[n]插入到左边的对应位置
def insertSort(arr,length)
  #递归的最小情况,直接返回
  if length==1
    return arr
  else
    #排序左边
    #sort left
    arr=insertSort(arr,length-1)
    element=arr[length-1]
    #插入右边的值到左边已经排序好的数组中
    #insert element to left
    index=length-2
    while index>=0 and arr[index]>element
      arr[index+1]=arr[index]
      index-=1
    end
    arr[index+1]=element
  end
  arr
end
puts insertSort(arr,arr.length).to_s

要注意一点就是递归不一定是更优化的写法,即使是在不计函数调用开销的情况下,递归也可能比常规方法更慢,但是递归为我们思考某个问题提供了一个更好的思路,在面对某些问题时,递归可以使问题变的异常简单。

虽然递归不一定更快,不过很多效率比较高的分治算法都需要使用到递归(或者说不用递归相当难写)

欢迎关注我的github https://github.com/luckyCatMiao

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹