算法 经典排序算法资料及 ruby 实现

suffering · 发布于 2014年7月18日 · 最后由 arth 回复于 2015年7月17日 · 12243 次阅读
709
本帖已被设为精华帖!

经典排序算法资料及ruby实现

学习<算法导论>时到网络上找了一批排序算法的资料. 结合参考资料分别用ruby写了一遍. 这里分享给大家. 配上图与参考资料.

插入排序

insert sort insert sort

def insert_sort!
  (0...self.length).to_a.each do |j|
    key = self[j]
    i = j - 1;
    while i >= 0 and self[i] > key
      self[i+1] = self[i]
      i = i-1
    end
    self[i+1] = key
  end
  self
end

冒泡排序

buble sort

buble sort

wikipedia 详解: http://en.wikipedia.org/wiki/Insertion_sort

Problem Solving: Searching and sorting

def bubble_sort!
  f = 1
  while f < self.length
    (0...(self.length-f)).to_a.each do |i|
      self[i], self[i+1] = self[i+1], self[i] if self[i] > self[i+1]
    end
    f += 1
  end
  self
end

鸡尾酒排序

cocktail sort

wikipedia 详解: http://en.wikipedia.org/wiki/Cocktail_sort

def cocktail_sort!
    f  = 0
    while f < self.length/2
      i = 0
      while i < self.length - 1
        self[i], self[i+1] = self[i+1], self[i] if self[i] > self[i+1]
        i += 1;
      end
      t = self.length - 1
      while t > 0
         self[t], self[t-1] = self[t-1], self[t] if self[t] < self[t-1]
         t -= 1
      end 
      f += 1
    end
    self
  end

合并排序

merge sort

merge sort

wikipedia 详解: http://en.wikipedia.org/wiki/Merge_sort

def merge_sort!
  return self if self.size <= 1
  left = self[0, self.size/2]
  right = self[self.size/2, self.size - self.size/2]
  Array.merge(left.merge_sort, right.merge_sort)
end

def self.merge(left, right)
  sorted = []
  until left.empty? or right.empty?
      sorted << (left.first <= right.first ? left.shift : right.shift)
  end
  sorted + left + right
end

快速排序

quick sort

quick sort

wikipedia详解: http://en.wikipedia.org/wiki/Quicksort

三种qicksort的实现方式: http://c2.com/cgi/wiki?QuickSortInRuby

在线图示加语音详解: http://www.csanimated.com/animation.php?t=Quicksort

def quick_sort!
  return [] if self.empty?
  x, *a = self
  left, right = a.partition{|t| t < x}
  left.quick_sort + [x] + right.quick_sort
end

heapSort

heap sort

heap sort

wikipedia 详解: http://en.wikipedia.org/wiki/Heapsort

更深入分析: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

def heap_sort!
  # in pseudo-code, heapify only called once, so inline it here
  ((length - 2) / 2).downto(0) {|start| siftdown(start, length - 1)}

  # "end" is a ruby keyword
  (length - 1).downto(1) do |end_|
    self[end_], self[0] = self[0], self[end_]
    siftdown(0, end_ - 1)
  end
  self
end

def siftdown(start, end_)
  root = start
  loop do
    child = root * 2 + 1
    break if child > end_
    if child + 1 <= end_ and self[child] < self[child + 1]
      child += 1
    end
    if self[root] < self[child]
      self[root], self[child] = self[child], self[root]
      root = child
    else
      break
    end
  end
end

最后, 附上完整的ruby实现:

class Array
  # 插入排序
  def insert_sort!
    (0...self.length).to_a.each do |j|
      key = self[j]
      i = j - 1;
      while i >= 0 and self[i] > key
        self[i+1] = self[i]
        i = i-1
      end
      self[i+1] = key
    end
    self
  end

  # 快速排序
  def quick_sort!
    return [] if self.empty?
    x, *a = self
    left, right = a.partition{|t| t < x}
    left.quick_sort + [x] + right.quick_sort
  end

  # 冒泡排序
  def bubble_sort!
    f = 1
    while f < self.length
      (0...(self.length-f)).to_a.each do |i|
        self[i], self[i+1] = self[i+1], self[i] if self[i] > self[i+1]
      end
      f += 1
    end
    self
  end

  # 鸡尾酒排序(>_<)
  def cocktail_sort!
    f  = 0
    while f < self.length/2
      i = 0
      while i < self.length - 1
        self[i], self[i+1] = self[i+1], self[i] if self[i] > self[i+1]
        i += 1;
      end
      t = self.length - 1
      while t > 0
         self[t], self[t-1] = self[t-1], self[t] if self[t] < self[t-1]
         t -= 1
      end 
      f += 1
    end
    self
  end

  # 合并排序
  def merge_sort!
    return self if self.size <= 1
    left = self[0, self.size/2]
    right = self[self.size/2, self.size - self.size/2]
    Array.merge(left.merge_sort, right.merge_sort)
  end

  def self.merge(left, right)
    sorted = []
    until left.empty? or right.empty?
        sorted << (left.first <= right.first ? left.shift : right.shift)
    end
    sorted + left + right
  end

  # heap排序
  def heap_sort!
    # in pseudo-code, heapify only called once, so inline it here
    ((length - 2) / 2).downto(0) {|start| siftdown(start, length - 1)}

    # "end" is a ruby keyword
    (length - 1).downto(1) do |end_|
      self[end_], self[0] = self[0], self[end_]
      siftdown(0, end_ - 1)
    end
    self
  end

  def siftdown(start, end_)
    root = start
    loop do
      child = root * 2 + 1
      break if child > end_
      if child + 1 <= end_ and self[child] < self[child + 1]
        child += 1
      end
      if self[root] < self[child]
        self[root], self[child] = self[child], self[root]
        root = child
      else
        break
      end
    end
  end

  %w(insert quick bubble cocktail merge heap).each do |metd|
    define_method("#{metd}_sort") do
      self.dup.send("#{metd.to_s}_sort!") 
    end
  end
end

p b = ((1..100).to_a + (20..80).to_a).shuffle.sample(19)
p b.methods.grep /_sort/
p b.insert_sort
p b.bubble_sort
p b.quick_sort
p b.cocktail_sort
p b.merge_sort
p b.heap_sort

>_< 请原谅我闪花了你的眼. 神马? 你觉得眼不花? 那看看这个吧: http://www.sorting-algorithms.com/

共收到 46 条回复
96

很形象!

2466

还少个shell排序。

7072

觉得算法什么的,可不可读都几乎没办法降低理解的难度。

9442

我想问,那图是用啥做的?

709

#4楼 @flowerwrong , 网络上找的. 我也不知道怎么做的呢 >_<

9800

正能量啊,社区很久没出现炼气的东西了,大部分资料都在练剑。。。。

4755

#3楼 @yfractal 图或者伪代码更好

7072

#6楼 @pynix 觉得树和图,实现的最大难点在递归。 #7楼 @Martin91 是啊!

11222

@flowerwrong 用Fireworks就可以做,一幅幅画好,然后设好顺序和帧数就可以了。

4798

如果我能早点看到这篇文章,也不会被豆瓣鄙视了。赞

681

#6楼 @pynix 因为ruby很多东西都包装好了。直接 xxx.sort

3347

请问一般面试程序员排序算法是算法里面最常考的吗?

4594

#12楼 @ted 应该比较经常,特别是快速排序。

2454

赞一个

14143

很不错的 技巧, 赞一个

5935

很直观,正好参考,赞

8134

好东西。谢谢分享! 刚才随机了10000个数据 看了一下运行时间,不同的方法之间的时间差真的很大很大!

12224

赞 :plus1:

9861

图太快

9861

#18楼 @zjyzxun 那个时间最快?

8134

#21楼 @wangping 一万个数据排序的时间如下: heap_sort:0.2s quick_sort:0.2s merge_sort:0.2s insert_sort:5.2s bubble_sort:19.1s cocktail_sort:22.1s 为了区分前三个排序的效率,我又随机了十万个数据,运行时间如下: quick_sort:0.7s merge_sort:0.8s heap_sort:1.5s

现在明白为什么叫“快速”排序了

709

http://www.sorting-algorithms.com/ (墙外) 里其实有不同的排序算法的排序图示的. 可以很显示的显示不同排序的动画效果. 其中展示了, Random, Nearly Sorted, Reversed, Few Unique四种数据的排序情况. 点击左上角的图标, 表格内的所有图会同时开始排序动画. 很直观. 站点内也有各种算法的伪代码.

709

附上我机器的benchmark截图吧: (测试的代码用的上面帖出的代码, 我自己写的, 只是实现了算法, 很明显, 不是最高效版) 这份测试将self.dump的时间也算在内, 真正的排序速度实际上是用!版本的方法.

96

很形象生动呢亲~

756

@suffering merge_sort不加叹号的版本的实现在哪?只见带叹号的定义以及不带叹号的引用,quick_sort也是

709

#26楼 @psvr , 代码如下, 用的动态定义:

%w(insert quick bubble cocktail merge heap).each do |metd|
    define_method("#{metd}_sort") do
      self.dup.send("#{metd.to_s}_sort!") 
    end
  end

在全代码的最后几行. 一个一个去定义太傻了不是吗? DRY原则在这里也适用的. 😄

756

#27楼 @suffering 多谢!sorry疏忽了没看到这一段

8130

#merge_sort! 中的 right = self[self.size/2, self.size - self.size/2] 看起来太烦了,建议改成right = self - left

709

#29楼 @dalang , 3Q, 谢谢提醒. 但是这样是不行的. 比如说, a = [1, 1, 2, 4], left = [1]. 那么,right = a - left, 得到的值是[2, 4], 很明显这样是不对的.

8130

#30楼 @suffering 嗯 是我考虑不周。

709

#31楼 @dalang , 如果你实在受不了那种写法, 有一种写法倒是可以的: left, right = self.each_slice((self.length/2.0).ceil).to_a 测试代码如下:

class  Array
  def zslice
    self.each_slice((self.length/2.0).ceil).to_a
  end  
end  
a = [1, 2, 3]
b = [1, 2, 3, 4]
a.zslice #=> [[1, 2], [3]]
b.zslice #=> [[1, 2], [3, 4]]

这种写法, 一行搞定了问题, 看起来是否舒服得多?(对强迫症病患者 😄 )

8130

#32楼 @suffering 学习了,不过仔细想想,还是你原来的方式更好些,一看就明白。

910

http://developer.51cto.com/art/201407/444151.htm 和这个一起看,是不是更好!

2466

给个好看的快排。:-)

(defn qsort [[pivot & xs]]
  (when pivot
    (let [smaller #(< % pivot)]
      (lazy-cat (qsort (filter smaller xs))
        [pivot]
        (qsort (remove smaller xs))))))
8630

以前大学的时候学过也自己写过快排,冒泡。 现在不是都有现成的方法可以用么,为什么还要自己手工实现?

709

@zjwzszh , 一个简单问题的多角度解决方案. 重要的是在这个教程中所体现的思维方式.

96

#10楼 @hmilym 啊请问豆瓣考Ruby吗?还以为他们是Python架的呀?

4798

#38楼 @VVCepheiA 豆瓣不用ruby,我说的是豆瓣靠算法

10316

那些柱状图真是闪花眼,太快根本看不清。

15307

很棒,一直想要的东西

96

很棒!不过我是ruby菜鸟,有没有什么好的书或网站可以给推荐推荐。跪谢。

709

#42楼 @ekin <算法导论>

96

#43楼 @suffering 我去当当看看,多谢。

10937

鸡尾酒排序代码中,已经排序好的不用再遍历了

def cocktail_sort!
    f  = 0
    while f < self.length/2
        i = f
        while i < self.length - 1 - f
            self[i], self[i+1] = self[i+1], self[i] if self[i] > self[i+1]
            i += 1;
        end
        t = self.length - 1 - f
        while t > f
            self[t], self[t-1] = self[t-1], self[t] if self[t] < self[t-1]
            t -= 1
        end
        f += 1
    end
    self
end
16207

很有用,mark下以后看

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册