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

suffering · 发布于 2014年07月18日 · 最后由 arth 回复于 2015年07月17日 · 12701 次阅读

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

### 插入排序

``````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
``````

### 冒泡排序

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
``````

### 鸡尾酒排序

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
``````

### 合并排序

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
``````

### 快速排序

wikipedia详解: http://en.wikipedia.org/wiki/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

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

``````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
``````

``````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/

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

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

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

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

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

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

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

#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

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

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

#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
``````

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

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

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

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

#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]]
``````

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

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

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

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

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

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

#42楼 @ekin <算法导论>

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

``````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
``````