Ruby实现的各种排序算法

172 阅读 0 评论 114 点赞

我是靠谱客的博主典雅指甲油，最近开发中收集的这篇文章主要介绍Ruby实现的各种排序算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

时间复杂度：Θ(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]