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) 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.44,0.55,0.01,0.98,0.1234567] p bucket_sort(a) # Result: [0,0.1234567,0.75,0.98] (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |