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