Ruby实现的各种排序算法
时间复杂度：Θ(n^2)Bubble sortSelection sortInsertion sortShell sort时间复杂度：Θ(n*logn)Merge sortHeap sortQuick sort时间复杂度：Θ(n)Counting sortRadix sortBucket sort普通版本的快速排序：快速排序的随机化版本：快速排序的利用了Ruby的语法糖的随机化版本
时间复杂度：Θ(n^2)
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
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
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
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)
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
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
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)
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
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
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]
普通版本的快速排序：
arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s
def QuickSort(arrayInt, first, last)
if first < last
middle = Partition(arrayInt, first, last)
QuickSort(arrayInt, first, middle - 1)
QuickSort(arrayInt, middle + 1, last)
end
end
def Partition(arrayInt, first, last)
x = arrayInt[last]
i = first - 1
for j in first .. (last - 1)
if arrayInt[j] <= x
i += 1
arrayInt[i], arrayInt[j] = arrayInt[j], arrayInt[i] #exchange
end
end
arrayInt[i + 1], arrayInt[last] = arrayInt[last], arrayInt[i + 1]
return i + 1
end
QuickSort(arrayInt, 0, arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s
快速排序的随机化版本：
#example:
#The original array is：[14, 47, 46, 49, 82, 76, 92, 22, 44, 81, 59, 61]
#The sorted array is: [14, 22, 44, 46, 47, 49, 59, 61, 76, 81, 82, 92]
arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s
def RandomizedQuickSort(arrayInt, first, last)
if first < last
middle = RandomizedPartition(arrayInt, first, last)
RandomizedQuickSort(arrayInt, first, middle - 1)
RandomizedQuickSort(arrayInt, middle + 1, last)
end
end
def RandomizedPartition(arrayInt, first, last)
i = rand(last - first + 1) + first
arrayInt[i], arrayInt[last] = arrayInt[last], arrayInt[i]
return Partition(arrayInt, first, last)
end
def Partition(arrayInt, first, last)
x = arrayInt[last]
i = first - 1
for j in first .. (last - 1)
if arrayInt[j] <= x
i += 1
arrayInt[i], arrayInt[j] = arrayInt[j], arrayInt[i] #exchange
end
end
arrayInt[i + 1], arrayInt[last] = arrayInt[last], arrayInt[i + 1]
return i + 1
end
RandomizedQuickSort(arrayInt, 0, arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s
快速排序的利用了Ruby的语法糖的随机化版本
#example:
#The original array is：[14, 47, 46, 49, 82, 76, 92, 22, 44, 81, 59, 61]
#The sorted array is: [14, 22, 44, 46, 47, 49, 59, 61, 76, 81, 82, 92]
arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s
def RandomizedQuickSort(a)
i = rand(a.length)
a[i], a[a.length - 1] = a[a.length - 1], a[i]
(x=a.pop) ? RandomizedQuickSort(a.select{|i| i <= x}) + [x] + RandomizedQuickSort(a.select{|i| i > x}) : []
end
puts "The sorted array is: " + RandomizedQuickSort(arrayInt).to_s