Ruby 大神帮看看这个插入排序有什么问题

secondrocker · 2014年04月15日 · 最后由 secondrocker 回复于 2014年04月15日 · 2446 次阅读
def insertSort(left=[],arr)
    return left unless (x=arr.pop)
    left.each_with_index do |l,i|
        if l>x
            left.insert i,x
            return insertSort left,arr
        end
    end
    left.push x
    return insertSort left,arr
end
arr=[]
arrE=(1..10000).to_a
10000.times do |t|
    tmp=rand(arrE.count)
    arr.push (arrE.delete_at tmp)
end
puts (insertSort arr)

数组数量小于 900 没问题,大于 900 就会报 stack level too deep (SystemStackError) 大神帮看看什么问题

...栈溢出呗。。。递归的问题。。。

#1 楼 @Kabie 那么,哪块有问题呢?

#1 楼 @Kabie 而且同样的思路,用c#实现,完全木有问题~~

#1 楼 @Kabie c#代码

public static List<int> insertSort(List<int> left,List<int> arr)
{ 
  if(arr.Count==0)
  {
    return left;
  }
  var x=arr[arr.Count-1];
  arr.Remove(x);
  for(int i=0;i<left.Count;i++)
  {
    if(left[i]>x)
    {
      left.Insert(i,x);
      return insertSort(left,arr);
    }
  }
  left.Add(x);
  return insertSort(left,arr);
}

用循环啊。。。可能 ruby 栈小吧

。。。。。要递归用 reduce 就好了……

[7,5,1,2,4,3,6].reduce([]) { |arr, x|
  i = arr.index {|e| e > x }
  if i
    arr.insert(i, x)
  else
    arr.push(x)
  end
}

如果一定要递归,那就

$ export RUBY_THREAD_VM_STACK_SIZE=200000000
$ ruby insert_sort.rb

#8 楼 @santochancf #7 楼 @Kabie 如果是堆栈的问题,那么为什么下面的快速排序的代码没有问题呢?

def f(a)
  (x=a.pop)? f(a.select{|i| i <= x}) + [x] + f(a.select{|i| i > x}) : []
end

#8 楼 @santochancf #7 楼 @Kabie 难道是快速排序递归的次数较少?

#9 楼 @secondrocker 因为层数少啊。。。

#11 楼 @Kabie 莫非是因为主要工作由 select 做了,感谢大神了~

感谢大家解惑~

需要 登录 后方可回复, 如果你还没有账号请 注册新账号