Ruby实现的3种快速排序算法
刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~
话说Ruby可真是超厉害,好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。
期间我遇到了invalidmultibytechar(US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8
这个错误在stackoverflow上有人问到过,某人给出的回答是
Write#encoding:utf-8ontopofthatfile.Thatchangesthedefaultencodingofallstring/regexpliteralsinthatfileutf-8.
参考链接:http://stackoverflow.com/questions/3678172/ruby-1-9-invalid-multibyte-char-us-ascii
快速排序的普通版本:
#encoding:utf-8 #author:xujin,4100213 #date:Oct20,2012 #RandomizedQuickSort #tosortanarraybyusingQuickSort #example: #Theoriginalarrayis:[10,35,25,67,69,52,24,40,69,76,6,49] #Thesortedarrayis:[6,10,24,25,35,40,49,52,67,69,69,76]
arrayInt=Array.new index=0 while(index<12) arrayInt[index]=rand(100) #produce12randomnumber index+=1 end puts"Theoriginalarrayis:"+arrayInt.to_s
defQuickSort(arrayInt,first,last) iffirst<last middle=Partition(arrayInt,first,last) QuickSort(arrayInt,first,middle-1) QuickSort(arrayInt,middle+1,last) end end
defPartition(arrayInt,first,last) x=arrayInt[last] i=first-1 forjinfirst..(last-1) ifarrayInt[j]<=x i+=1 arrayInt[i],arrayInt[j]=arrayInt[j],arrayInt[i] #exchange end end arrayInt[i+1],arrayInt[last]=arrayInt[last],arrayInt[i+1] returni+1 end
QuickSort(arrayInt,0,arrayInt.length-1) puts"Thesortedarrayis:"+arrayInt.to_s