1、Bubble sort 冒泡排序
# Bubble sort 冒泡排序
# 每次扫描，比较和交换相邻元素，保证一次扫描后，最大元素在最后一个
# 每次扫描后，扫描队列长度减一
# Time Complexity: О(n^2)
# Space Complexity: О(n) total, O(1) auxiliary
# Stable: Yes
def bubble_sort(container)
swap=true
while(swap)
swap=false
for i in 0..(container.size-1) do
for j in 0..i do
if(container[i]<container[j])
r=container[j]
container[j]=container[i]
container[i]=r
swap=true
end
end
end
end
return container
end
2、Selection sort 选择排序
# Selection sort 选择排序
# 从头扫描到尾，每次将最小元素放到第一个
# 每次扫描后，队列长度减一
# Time Complexity: О(n^2)
# Space Complexity: О(n) total, O(1) auxiliary
# Stable: Yes
def selection_sort(container)
for i in 0..container.size-1 do
min = i
for j in i..container.size-1 do
if(container[min]>container[j])
min=j
end
end
r=container[i]
container[i]=container[min]
container[min]=r
end
return container
end
3、Insertion sort 插入排序
# Insertion sort 插入排序
# 起始队列长度为1，每次向队列增加1个数字
# 通过元素移动，将队列调整为有序状态
# Time Complexity: О(n^2)
# Space Complexity: О(n) total, O(1) auxiliary
# Stable: Yes
def insertion_sort(container)
if container.size <2
return container
end
for i in 1..container.size-1 do
val = container[i]
j=i-1
while(j>=0 and container[j]>val) do
container[j+1]=container[j]
j=j-1
end
container[j+1] = val
end
return container
end
4、Shell Sort 希尔排序
# Shell Sort 希尔排序
# 指定一个步长，将需要排序的数字，按序号%步长分组
# 对每组进行插入排序，然后减小步长，再次分组，排序
# 直到步长为1结束
# Time Complexity: О(n^2)
# Space Complexity: О(n) total, O(1) auxiliary
# Stable: Yes
def shell_sort(container)
step = container.size/2
while step>0 do
for i in step..container.size-1 do
val= container[i]
j=i-step
while(j>=0 and container[j]>val) do
container[j+step] = container[j]
j=j-step
end
container[j+step]=val
end
#puts(">>")
#puts(container)
step = step/2
end
return container
end
5、Merge sort 归并排序
# Merge sort 归并排序
# 二路归并首先将归并长度定为2，在归并集内进行排序
# 然后归并长度×2，将有序集合进行归并
# Time Complexity: О(nlogn) average and worst-case
# Space Complexity: О(n) auxiliary
# Stable: Yes
def mergesort(container)
return container if container.size <= 1
mid = container.size / 2
left = container[0...mid]
right = container[mid...container.size]
merge(mergesort(left), mergesort(right))
end
private
def merge(left, right)
sorted = []
until left.empty? or right.empty?
left.first <= right.first ? sorted << left.shift : sorted << right.shift
end
sorted + left + right
end