各种排序的Ruby实现 博客分类: Ruby RubyJ#performance
程序员文章站
2024-02-22 16:54:22
...
Θ(n^2)
1, Bubble sort
2, Selection sort
3, Insertion sort
4, Shell sort
Θ(n*logn)
1, Merge sort
2, Heap sort
3, Quick sort
Θ(n)
1, Counting sort
2, Radix sort
3, Bucket sort
1, Bubble sort
def bubble_sort(a) (a.size-2).downto(0) do |i| (0..i).each do |j| a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1] end end return a end
2, Selection sort
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
3, Insertion sort
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, Shell sort
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
Θ(n*logn)
1, Merge sort
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
2, Heap sort
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
3, Quick sort
def quick_sort(a) (x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : [] end
Θ(n)
1, Counting sort
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
2, Radix sort
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
3, Bucket sort
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]
推荐阅读
-
Rails程序开发的最大问题是代码规范 博客分类: Ruby Rails敏捷开发招聘Ruby单元测试
-
基于ruby-protobuf的rpc示例 博客分类: Ruby RubyGoogle
-
各种排序的Ruby实现 博客分类: Ruby RubyJ#performance
-
URL/HTML/JavaScript的encode/escape 博客分类: Ruby HTMLJavaScriptRubyCGIjQuery
-
Ruby导出xls和csv的utf-8问题的解决 博客分类: Ruby RubyExcel
-
selenium和ajax的测试问题 博客分类: ruby on rails AjaxRailsRubyJavaScriptChrome
-
我的第三个ruby on rails网站发布了 博客分类: ruby RailsRuby
-
我的第三个ruby on rails网站发布了 博客分类: ruby RailsRuby
-
[提问]ruby的项目如何维持代码的统一性和可维护性? 博客分类: 其它 RubyPerl.netCC++
-
Ruby,Python不能威胁到Java的13个理由 博客分类: 编程技术 JavaRubyPythonGroovyScala