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