各种排序的Ruby实现

Θ(n^2)

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]

评论

2 楼 q1241312 2012-10-20  

厉害，快速排序用循环实现了，不知道时间复杂度是多少。

1 楼 gemstone 2008-11-27  

很不错， 这里也有个实现。

require 'containers/heap' # for heapsort
 
=begin rdoc
This module implements sorting algorithms. Documentation is provided for each algorithm.
=end
module Algorithms::Sort
  # Bubble sort: A very naive sort that keeps swapping elements until the container is sorted.
  # Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should
  # be implemented for the container.
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.bubble_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.bubble_sort(container)
    loop do
      swapped = false
      (container.size-1).times do |i|
        if (container[i] <=> container[i+1]) == 1
          container[i], container[i+1] = container[i+1], container[i] # Swap
          swapped = true
        end
      end
      break unless swapped
    end
    container
  end
  
  # Comb sort: A variation on bubble sort that dramatically improves performance.
  # Source: http://yagni.com/combsort/
  # Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should
  # be implemented for the container.
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.comb_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.comb_sort(container)
    container
    gap = container.size
    loop do
      gap = gap * 10/13
      gap = 11 if gap == 9 || gap == 10
      gap = 1 if gap < 1
      swapped = false
      (container.size - gap).times do |i|
        if (container[i] <=> container[i + gap]) == 1
          container[i], container[i+gap] = container[i+gap], container[i] # Swap
          swapped = true
        end
      end
      break if !swapped && gap == 1
    end
    container
  end
  
  # Selection sort: A naive sort that goes through the container and selects the smallest element,
  # putting it at the beginning. Repeat until the end is reached.
  # Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should
  # be implemented for the container.
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.selection_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.selection_sort(container)
    0.upto(container.size-1) do |i|
      min = i
      (i+1).upto(container.size-1) do |j|
        min = j if (container[j] <=> container[min]) == -1
      end
      container[i], container[min] = container[min], container[i] # Swap
    end
    container
  end
  
  # Heap sort: Uses a heap (implemented by the Containers module) to sort the collection.
  # Requirements: Needs to be able to compare elements with <=>
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.heapsort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.heapsort(container)
    heap = Containers::Heap.new(container)
    ary = []
    ary << heap.pop until heap.empty?
    ary
  end
  
  # Insertion sort: Elements are inserted sequentially into the right position.
  # Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should
  # be implemented for the container.
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.insertion_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.insertion_sort(container)
    return container if container.size < 2
    (1..container.size-1).each do |i|
      value = container[i]
      j = i-1
      while j >= 0 and container[j] > value do
        container[j+1] = container[j]
        j = j-1
      end
      container[j+1] = value
    end
    container
  end
  
  # Shell sort: Similar approach as insertion sort but slightly better.
  # Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should
  # be implemented for the container.
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.shell_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.shell_sort(container)
    increment = container.size/2
    while increment > 0 do
      (increment..container.size-1).each do |i|
        temp = container[i]
        j = i
        while j >= increment && container[j - increment] > temp do
          container[j] = container[j-increment]
          j -= increment
        end
        container[j] = temp
      end
      increment = (increment == 2 ? 1 : (increment / 2.2).round)
    end
    container
  end
  
  # Quicksort: A divide-and-conquer sort that recursively partitions a container until it is sorted.
  # Requirements: Container should implement #pop and include the Enumerable module.
  # Time Complexity: О(n log n) average, O(n^2) worst-case
  # Space Complexity: О(n) auxiliary
  # Stable: No
  #
  # Algorithms::Sort.quicksort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  # def self.quicksort(container)
  # return [] if container.empty?
  #
  # x, *xs = container
  #
  # quicksort(xs.select { |i| i < x }) + [x] + quicksort(xs.select { |i| i >= x })
  # end
  
  def self.partition(data, left, right)
    pivot = data[front]
    left += 1
 
    while left <= right do
      if data[frontUnknown] < pivot
        back += 1
        data[frontUnknown], data[back] = data[back], data[frontUnknown] # Swap
      end
 
      frontUnknown += 1
    end
 
    data[front], data[back] = data[back], data[front] # Swap
    back
  end
 
 
  # def self.quicksort(container, left = 0, right = container.size - 1)
  # if left < right
  # middle = partition(container, left, right)
  # quicksort(container, left, middle - 1)
  # quicksort(container, middle + 1, right)
  # end
  # end
  
  def self.quicksort(container)
    bottom, top = [], []
    top[0] = 0
    bottom[0] = container.size
    i = 0
    while i >= 0 do
      l = top[i]
      r = bottom[i] - 1;
      if l < r
        pivot = container[l]
        while l < r do
          r -= 1 while (container[r] >= pivot && l < r)
          if (l < r)
            container[l] = container[r]
            l += 1
          end
          l += 1 while (container[l] <= pivot && l < r)
          if (l < r)
            container[r] = container[l]
            r -= 1
          end
        end
        container[l] = pivot
        top[i+1] = l + 1
        bottom[i+1] = bottom[i]
        bottom[i] = l
        i += 1
      else
        i -= 1
      end
    end
    container
  end
 
  # Mergesort: A stable divide-and-conquer sort that sorts small chunks of the container and then merges them together.
  # Returns an array of the sorted elements.
  # Requirements: Container should implement []
  # Time Complexity: О(n log n) average and worst-case
  # Space Complexity: О(n) auxiliary
  # Stable: Yes
  #
  # Algorithms::Sort.mergesort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
  def self.mergesort(container)
    return container if container.size <= 1
    mid = container.size / 2
    left = container[0...mid]
    right = container[mid...container.size]
    merge(mergesort(left), mergesort(right))
  end
 
  def self.merge(left, right)
    sorted = []
    until left.empty? or right.empty?
      left.first <= right.first ? sorted << left.shift : sorted << right.shift
    end
    sorted + left + right
  end
 
end

Source： http://github.com/kanwei/algorithms/tree/master