经典排序算法ruby实现
在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字数据以及产生人类可读的输出结果。
冒泡排序
简介
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。了解更多
ruby实现
def bubble_sort(array)
return array if array.size <= 1
swap = true
while swap
swap = false
(array.length - 1).times do |x|
if array[x] > array[x+1]
array[x], array[x+1] = array[x+1], array[x]
swap = true
end
end
end
array
end
插入排序
简介
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。了解更多
ruby实现
def insertion_sort(array)
(array.length).times do |j|
while j > 0
if array[j-1] > array[j]
array[j], array[j-1] = array[j-1], array[j]
else
break
end
j-=1
end
end
array
end
选择排序
简介
选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。了解更多
ruby实现
def selection_sort(array)
n = array.length - 1
n.times do |i|
min_index = i
for j in (i + 1)..n
min_index = j if array[j] < array[min_index]
end
array[i], array[min_index] = array[min_index], array[i] if min_index != i
end
array
end
归并排序
简介
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。了解更多
ruby实现
def merge_sort(array)
if array.length <= 1
array
else
mid = (array.length / 2).floor
left = merge_sort(array[0..mid-1])
right = merge_sort(array[mid..array.length])
merge(left, right)
end
end
def merge(left, right)
if left.empty?
right
elsif right.empty?
left
elsif left[0] < right[0]
[left[0]] + merge(left[1..left.length], right)
else
[right[0]] + merge(left, right[1..right.length])
end
end
快速排序
简介
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要 O(nlogn)次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序 (nlogn) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。了解更多
ruby实现
def quick_sort(array)
return array if array.length <= 1
pivot = array.delete_at(rand(array.length))
left = Array.new
right = Array.new
array.each do |x|
if x <= pivot
left << x
else
right << x
end
end
return *quick_sort(left), pivot ,*quick_sort(right)
end
堆排序
简介
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。了解更多
ruby实现
def heap_sort(array)
n = array.length
a = [nil] + array
(n / 2).downto(1) do |i|
heapify(a, i, n)
end
while n > 1
a[1], a[n] = a[n], a[1]
n -= 1
heapify(a, 1, n)
end
a.drop(1)
end
def heapify(array, parent, limit)
root = array[parent]
while (child = 2 * parent) <= limit
child += 1 if child < limit && array[child] < array[child + 1]
break if root >= array[child]
array[parent], parent = array[child], child
array[parent] = root
end
end