`
fireflyman
  • 浏览: 118427 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

Ruby排序算法收集

    博客分类:
  • ROR
阅读更多
1.冒泡排序

百科:http://baike.baidu.com/view/254413.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

def bubble_sort(arr)
  1.upto(arr.length-1) do |i|
    (arr.length-i).times do |j|
      if arr[j]>arr[j+1]
        arr[j],arr[j+1] = arr[j+1],arr[j]
      end
    end
  end
    arr
end

array = [2.3,1.3,15.02,25.02,45,85.14,56.1,35.2,4.2,15.4]
puts bubble_sort(array)


2.漢諾塔
百科:http://baike.baidu.com/view/191666.html?wtp=tt
Wiki: http://zh.wikipedia.org/zh-tw/%E6%B1%89%E8%AF%BA%E5%A1%94

def move(from,to)
  puts "#{from} move to #{to}"
end

def hanoi(n,first,second,third)
  if n==1
    move(first,third)
  else
    hanoi(n-1,first,third,second)
    move(first,third)
    hanoi(n-1,second,first,third)
  end
end

hanoi(6,"A","B","C")


3.插入排序
百科:http://baike.baidu.com/view/396887.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

def insertion_sort(a)  
    a.each_with_index do |el,i|  
      j = i - 1  
        while j >= 0  
          break if a[j] <= el  
          a[j + 1] = a[j]  
          j -= 1  
        end  
      a[j + 1] = el  
    end  
    return a  
  end  


4.選擇排序
百科:http://baike.baidu.com/view/547263.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

def selection_sort(a)
  b = []
  a.size.times do |i|
    min = a.min
    b << min
    a.delete_at(a.index(min))
  end
  return b
end


5.Shell排序
百科:http://baike.baidu.com/view/549624.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

def shell_sort(a)
  gap = a.size
  while(gap > 1)
    gap = gap / 2
    (gap..a.size-1).each do |i|
      j = i
      while(j > 0)
        a[j], a[j-gap] = a[j-gap], a[j] if a[j] <= a[j-gap]
        j = j - gap
      end
    end
  end
  return a
end


6.合并排序
百科:http://baike.baidu.com/view/3668564.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F

def merge(l, r)
  result = []
  while l.size > 0 and r.size > 0 do
    if l.first < r.first
      result << l.shift
    else
      result << r.shift
    end
  end
  if l.size > 0
    result += l
  end
  if r.size > 0
    result += r
  end
  return result
end

def merge_sort(a)
  return a if a.size <= 1
  middle = a.size / 2
  left = merge_sort(a[0, middle])
  right = merge_sort(a[middle, a.size - middle])
  merge(left, right)
end


7.堆排序
百科:http://baike.baidu.com/view/157305.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%A0%86%E6%8E%92%E5%BA%8F

def heapify(a, idx, size)
  left_idx = 2 * idx + 1
  right_idx = 2 * idx + 2
  bigger_idx = idx
  bigger_idx = left_idx if left_idx < size && a[left_idx] > a[idx]
  bigger_idx = right_idx if right_idx < size && a[right_idx] > a[bigger_idx]
  if bigger_idx != idx
    a[idx], a[bigger_idx] = a[bigger_idx], a[idx]
    heapify(a, bigger_idx, size)
  end
end

def build_heap(a)
  last_parent_idx = a.length / 2 - 1
  i = last_parent_idx
  while i >= 0
    heapify(a, i, a.size)
    i = i - 1
  end
end

def heap_sort(a)
  return a if a.size <= 1
  size = a.size
  build_heap(a)
  while size > 0
    a[0], a[size-1] = a[size-1], a[0]
    size = size - 1
    heapify(a, 0, size)
  end
  return a
end


8.快速排序
百科:http://baike.baidu.com/view/115472.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

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


9.計數排序
百科:http://baike.baidu.com/view/1209480.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F

def counting_sort(a)
  min = a.min
  max = a.max
  counts = Array.new(max-min+1, 0)

  a.each do |n|
    counts[n-min] += 1
  end

  (0...counts.size).map{|i| [i+min]*counts[i]}.flatten
end


10.基數排序
百科:http://baike.baidu.com/view/1170573.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

def kth_digit(n, i)
  while(i > 1)
    n = n / 10
    i = i - 1
  end
  n % 10
end

def radix_sort(a)
  max = a.max
  d = Math.log10(max).floor + 1

  (1..d).each do |i|
    tmp = []
    (0..9).each do |j|
      tmp[j] = []
    end

    a.each do |n|
      kth = kth_digit(n, i)
      tmp[kth] << n
    end
    a = tmp.flatten
  end
  return a
end


11.桶排序
百科:http://baike.baidu.com/view/1784217.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E6%A1%B6%E6%8E%92%E5%BA%8F

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

def first_number(n)
  (n * 10).to_i
end

def bucket_sort(a)
  tmp = []
  (0..9).each do |j|
    tmp[j] = []
  end
  
  a.each do |n|
    k = first_number(n)
    tmp[k] << n
  end

  (0..9).each do |j|
    tmp[j] = quick_sort(tmp[j])
  end

  tmp.flatten
end

a = [0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567]
p bucket_sort(a)

# Result: 
[0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]


12.雞尾酒排序
百科:http://baike.baidu.com/view/1981861.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F

13.奇偶排序
百科:http://baike.baidu.com/view/2096179.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E5%A5%87%E5%81%B6%E6%8E%92%E5%BA%8F


14.鴿巢排序
百科:http://baike.baidu.com/view/2020276.html?wtp=tt
Wiki:http://zh.wikipedia.org/zh-tw/%E9%B8%BD%E5%B7%A2%E6%8E%92%E5%BA%8F
分享到:
评论
7 楼 changyy_1988 2010-09-07  
只是用过JaVa的一些排序,学习了
6 楼 yangzhihuan 2010-09-01  
kaka2008 写道
a,b=b,a


这样的写法听ns说过,相当的奇妙
小飞人,你好猛


我刚学编程的时候,最记得上课时的一个题目就是用 C 语言在不准用临时变量的情况下,实现a,b=b,a,当然a,b是int类型。

那时一直觉得这个很牛叉,后来学了Ruby之学,居然直接在语言级别就有了,令我少了很多乐趣,哈哈。
5 楼 deng131 2010-08-29  
tianlang0101 写道
太猛了。~     

太猛了。~     
4 楼 tianlang0101 2010-08-27  
太猛了。~     
3 楼 MySpace 2010-08-26  
你是我滴玫瑰 你是我滴花
2 楼 fireflyman 2010-08-26  
代碼基本上都是別人寫的...跟我關系不大..
1 楼 kaka2008 2010-08-26  
a,b=b,a


这样的写法听ns说过,相当的奇妙
小飞人,你好猛

相关推荐

    Ruby Locale-开源

    Ruby Locale 是一个开源项目,专为 Ruby 解释器设计,旨在增强其对语言环境(locale)的支持。在软件开发中,语言环境是一个关键组件,它决定了应用程序如何处理日期、时间、数字格式、货币符号以及文本的排序和翻译...

    最新秋招freewheeljava笔试题.docx

    4. **冒泡排序优化**:可以使用双指针法或比较次数更少的优化算法,如快速排序、归并排序等。 以上就是这份笔试题中涉及的IT知识点,包括分布式系统、大数据、广告投放、机器学习、全栈开发、运维等多个方面。

    CodeWars-源码.rar

    2. **算法**:排序算法(冒泡排序、选择排序、快速排序、归并排序等)、搜索算法(线性搜索、二分搜索)、动态规划、贪心算法等。 3. **数据结构**:数组、链表、栈、队列、哈希表、树(二叉树、平衡二叉树、红黑树...

    SuperCollider-3.11.0-macOS-signed.zip 亲测可用:用于音频合成和算法合成的平台

    功能语言-sclang单一继承面向对象和函数式语言类似于Smalltalk或Ruby,语法类似于C或Javascript动态类型恒定时间消息查找和实时垃圾收集用作一流对象闭包是词法,作用域是词法和动态协程列表理解局部应用(显式计算...

    leetcode530-leetcode:一个为leetcode收集最佳解决方案的repo

    Ruby 1 算法 二和 简单的 :check_mark: :check_mark: :check_mark: 2 算法 加两个数 中等的 :check_mark: :check_mark: :check_mark: 7 算法 反转整数 简单的 :check_mark: :check_mark: :check_mark: 9 算法 回文数...

    comment-rollup

    4. **数据结构和算法**:为了有效聚合评论,可能使用了特定的数据结构(如数组、哈希或树)以及排序算法(如快速排序、归并排序)。这有助于根据时间、评分或其他标准组织评论。 5. **模板引擎**:为了展示评论,...

    millimas-ranking

    对于毫秒级别的排名功能,服务器可能采用了高效的排序算法,如快速排序、归并排序,或者利用数据库查询优化来实现。 在"millimas-ranking-master"这个文件名中,"master"通常代表项目的主分支,这表明这是一个Git...

    Codewars_Challenges:此仓库包含我对CodeWars平台面临的各种挑战的解决方案

    - 挑战通常涉及解决特定问题,如字符串处理、数学计算、排序算法等,以增强实际编程能力。 - 通过完成挑战,开发者可以获得积分(Kata等级)和社区的认可,从而激励持续学习。 2. **Java编程语言**: - Java是一...

    codewars-katas:我的Codewars Kata解决方案的集合。 不经常更新

    2. **算法与数据结构**:Kata经常涉及到排序、搜索、图论等经典算法,以及栈、队列、树等基本数据结构。通过研究这些解决方案,我们可以学习如何运用这些知识来解决实际问题,提升算法设计能力。 3. **测试驱动开发...

    citacoes

    8. **搜索功能**:一个全面的引用库可能会有搜索功能,涉及关键词匹配和排序算法,如Trie树或倒排索引。 9. **多语言支持**:如果引用来自不同语言,项目可能包含本地化和国际化策略,比如使用i18n库。 10. **版权...

    ELK-guide-cn.pdf

    - ES在运维监控领域的其他玩法:包括percolator api和watcher报警、ElastAlert、packetbeat抓包分析、时序数据库以及Etsy的Kale异常检测。 Logstash Logstash是ELK stack中的日志收集和处理工具。它能够从多个来源...

    java开源包1

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包11

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包2

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包3

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包6

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包5

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包10

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

    java开源包4

    Flume 是一个分布式、可靠和高可用的服务,用于收集、聚合以及移动大量日志数据,使用一个简单灵活的架构,就流数据模型。这是一个可靠、容错的服务。 彩信发送开发包 apimms apimms 提供了各种语言用来发送彩信...

Global site tag (gtag.js) - Google Analytics