发布于 2016-01-27 05:07:59 | 133 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Ruby教程,程序狗速度看过来!

Ruby编程语言

Ruby,一种为简单快捷的面向对象编程(面向对象程序设计)而创的脚本语言,在20世纪90年代由日本人松本行弘开发,遵守GPL协议和Ruby License。它的灵感与特性来自于 Perl、Smalltalk、Eiffel、Ada以及 Lisp 语言。


这篇文章主要介绍了Ruby实现的各种排序算法,本文给出了Bubble sort、Insertion sort、Selection sort、Shell sort等排序的实现方法,需要的朋友可以参考下

时间复杂度:Θ(n^2)

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 

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 

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  

 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)

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  

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 

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)

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  

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  

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]  



最新网友评论  共有(0)条评论 发布评论 返回顶部

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务