经典排序算法

Ruby 写经典排序算法,完整可参考 gwtw 网站:https://github.com/gwtw/ruby-sorting

另外 ,gwtw 网站有大多数排序算法的讲解与实现:http://www.growingwiththeweb.com/p/search.html?q=sort

以下为常见简单排序算法:

  1. 冒泡:形如冒泡,两两比较n轮,每轮都将最值置于顶端。稳定,时间复杂度 O(n ^ 2)
  2. 选择:形如选择,先确定一个数,将其余的数与其比较,发现最值则交换二者,执行 n 轮。不稳定,时间复杂度 O(n ^ 2)
  3. 插入:类似摸牌,一次取一个元素,并插入到正确位置。稳定,时间复杂度 O(n ^ 2)
  4. 快速:确定支点,递归地对支点左侧(相对支点的小者)和支点右侧(类似)进行快速排序。不稳定,期望时间复杂度 O(n lg n) ,最坏 O(n ^ 2)
  5. 归并:归并操作,将两组已排序好的序列合并,多用递归实现。(备注:通常序列的归并次数等于逆序对个数)。稳定,时间复杂度 O(n lg n),空间复杂度 O(n)
  6. 桶排序:鸽巢原理,将数组分到有限的桶里,每个桶再排序。稳定,数值均匀分配时,时间复杂度 O(n),空间复杂度 O(k)

参考:

#!/usr/bin/env ruby
# -*- encode: utf-8 -*-

'''
:author YanWen
:class  sorter
:last_modified 2018-09-23
'''

class Sorter

  # public static

  # :method Bubble sort
  # :params list(not references)
  def self.bubble list
    list = list.clone
    0.upto(list.size - 1) do |round|
      1.upto(list.size - round - 1) do |index|
        (list[index - 1], list[index] = list[index], list[index - 1]) if list[index - 1] > list[index]
      end
    end

    list
  end

  # :method Select sort
  # :params list(not references)
  def self.select list
    list = list.clone
    0.upto(list.size - 1) do |round|
      round.upto(list.size - 1) do |index|
        (list[round], list[index] = list[index], list[round]) if list[round] > list[index]
      end
    end

    list
  end

  # :method Insertion sort
  # :params list(not references)
  def self.insertion list
    list = list.clone
    1.upto(list.size - 1) do |round|
      item_fetched, index_inserted = list[round], 0

      # insert item_fetched into the sorted sequence
      round.downto(0) do |index|
        index_inserted = index; break if list[index - 1] <= item_fetched
        list[index] = list[index - 1]
      end
      list[index_inserted] = item_fetched
    end

    list
  end

  # :method Quick sort
  # :params list(not references)
  def self.quick list
    list = list.clone
    return list if list.size <= 1

    pivot = list.sample
    left, right = list.partition { |e| e < pivot }
    Sorter::quick(left) + Sorter::quick(right)
  end

  # :method Merge sort
  # :params list(not references)
  def self.merge list
    list = list.clone
    return list if list .size < 2

    pivot = list.size / 2

    # Merge
    lambda { |left, right|
      final = []
      until left.empty? or right.empty?
        final << if left.first < right.first; left.shift else right.shift end
      end
      final + left + right
    }.call Sorter::merge(list[0...pivot]), Sorter::merge(list[pivot..-1])
  end

  # :method Bucket
  # :params list(not references)
  def self.bucket list, bucket_size = 5
    list = list.clone
    return list if list .size < 2

    min_value = list.min
    max_value = list.max

    # Init buckets
    bucket_count = ((max_value - min_value) / bucket_size).floor + 1
    buckets = Array.new bucket_count
    buckets = buckets.map { || [] }

    # distribute input list values into buckets
    list.each do |value|
      buckets[((value - min_value) / bucket_size).floor].push value
    end

    # sort buckets and place back into input list
    list.clear
    buckets.each do |bucket|
      bucket = Sorter::bubble bucket
      bucket.each { |value| list.push value }
    end
  
    list
  end

  # Simple test
  def self.main list
    puts "Bubble     sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::bubble    list_cloned}"
    puts "Select     sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::select    list_cloned}"
    puts "Insertion  sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::insertion list_cloned}"
    puts "Quick      sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::quick     list_cloned}"
    puts "Merge      sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::merge     list_cloned}"
    puts "Bucket     sort: #{list.to_s} -> #{list_cloned = list.clone; Sorter::bucket    list_cloned}"
  end

end

Sorter::main [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8]

测试输出:

Bubble     sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]
Select     sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]
Insertion  sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]
Quick      sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]
Merge      sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]
Bucket     sort: [3.4, 5.6, 1.1, 9.6, 7.3, 1.0, 8.8] -> [1.0, 1.1, 3.4, 5.6, 7.3, 8.8, 9.6]

参考:

  1. https://github.com/gwtw/ruby-sorting
  2. http://www.growingwiththeweb.com/p/search.html?q=sort

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s