Ruby实现的各种排序算法
时间复杂度:Θ(n^2)
Bubblesort
defbubble_sort(a) (a.size-2).downto(0)do|i| (0..i).eachdo|j| a[j],a[j+1]=a[j+1],a[j]ifa[j]>a[j+1] end end returna end
Selectionsort
defselection_sort(a) b=[] a.size.timesdo|i| min=a.min b<<min a.delete_at(a.index(min)) end returnb end
Insertionsort
definsertion_sort(a) a.each_with_indexdo|el,i| j=i-1 whilej>=0 breakifa[j]<=el a[j+1]=a[j] j-=1 end a[j+1]=el end returna end
Shellsort
defshell_sort(a) gap=a.size while(gap>1) gap=gap/2 (gap..a.size-1).eachdo|i| j=i while(j>0) a[j],a[j-gap]=a[j-gap],a[j]ifa[j]<=a[j-gap] j=j-gap end end end returna end
时间复杂度:Θ(n*logn)
Mergesort
defmerge(l,r) result=[] whilel.size>0andr.size>0do ifl.first<r.first result<<l.shift else result<<r.shift end end ifl.size>0 result+=l end ifr.size>0 result+=r end returnresult end defmerge_sort(a) returnaifa.size<=1 middle=a.size/2 left=merge_sort(a[0,middle]) right=merge_sort(a[middle,a.size-middle]) merge(left,right) end
Heapsort
defheapify(a,idx,size) left_idx=2*idx+1 right_idx=2*idx+2 bigger_idx=idx bigger_idx=left_idxifleft_idx<size&&a[left_idx]>a[idx] bigger_idx=right_idxifright_idx<size&&a[right_idx]>a[bigger_idx] ifbigger_idx!=idx a[idx],a[bigger_idx]=a[bigger_idx],a[idx] heapify(a,bigger_idx,size) end end
defbuild_heap(a) last_parent_idx=a.length/2-1 i=last_parent_idx whilei>=0 heapify(a,i,a.size) i=i-1 end end defheap_sort(a) returnaifa.size<=1 size=a.size build_heap(a) whilesize>0 a[0],a[size-1]=a[size-1],a[0] size=size-1 heapify(a,0,size) end returna end