冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.doc

排序算法java版，速度排行：冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序文章分类:java编程 先推荐一篇关于排序算法的文章：/guogangj/archive/2009/11/13/100876.html本文思路部分来源于上篇文章，但测得的结果似乎不大相同，不知是因为java的缘故还是因为我算法的缘故，欢迎拍砖。复习排序，顺便比下各种算法的速度，榜单如下：1、冒泡排序2、简单选择排序3、直接插入排序4、折半插入排序5、希尔排序6、堆排序7、归并排序8、快速排序当然这是慢速排行，哈哈直接上图：单位毫秒数量冒泡排序简单选择排序直接插入排序折半插入排序希尔排序堆排序归并排序快速排序10000个1578125067225001516015000个345327651563531161516020000个6140454724538281616151625000个100797171396913133116151630000个1464110313557819063131163135000个2014114328789025633131321540000个25766183591009434224731313245000个324692406313062435947473147由于希尔排序,堆排序,归并排序,快速排序太快，以至于在上图几乎是条直线，故有了下面转为他们准备的加强版数量希尔排序堆排序归并排序快速排序100000个17214011093200000个469406235234300000个812703422375400000个11251031516531500000个14061282719656600000个18281703860859700000个253120631000968800000个2735245311401188900000个30472843139112661000000个33753187151614221100000个39223500162516091200000个44213954196918121300000个47974422200019531400000个53914797254720941500000个54375219262523281600000个62035546246924851700000个65325953284426721800000个7125642129842844补上代码：java代码 1. importjava.util.arraylist; 2. importjava.util.arrays; 3. importjava.util.list; 4. 5. /* 6. *插入排序:直接插入排序、折半插入排序和系尔排序 7. *交换排序:冒泡排序和快速排序 8. *选择排序:简单选择排序和堆排序 9. *归并排序:归并排序 10. * 11. *基本思想 12. *插入排序:将第n个记录插入到前面(n-1)个有序的记录当中。 13. *交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。 14. *选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。 15. * 16. *排序方法比较 17. *排序方法平均时间最坏时间辅助存储 18. *直接插入排序o(n2)o(n2)o(1) 19. *起泡排序o(n2)o(n2)o(1) 20. *快速排序o(nlog2n)o(n2)o(nlog2n) 21. *简单选择排序o(n2)o(n2)o(1) 22. *堆排序o(nlog2n)o(nlog2n)o(1) 23. *归并排序o(nlog2n)o(nlog2n)o(n) 24. *基数排序o(d(n+radix)o(d(n+radix)o(radix) 25. * 26. * 27. * 28. *authoradministrator 29. * 30. */31. publicclasssorttest 32. 33. publicstaticvoidmain(stringargs)throwsexception 34. /测试排序是否正确 35. /stringtesterr=newstring冒泡排序,简单选择排序,直接插入排序,折半插入排序,系尔排序,堆排序,归并排序,快速排序; 36. /newsorttest().testerr(testerr); 37. 38. /排序1（全部） 39. stringstrs=newstring冒泡排序,简单选择排序,直接插入排序,折半插入排序,希尔排序,堆排序,归并排序,快速排序; 40. newsorttest().test(strs,10000,50000,5000); 41. 42. /排序2（加强） 43. stringstrs2=newstring希尔排序,堆排序,归并排序,快速排序; 44. newsorttest().test(strs2,100000,1900000,100000); 45. 46. 47. privatevoidtesterr(stringstrings)throwsexception 48. 49. /system.out.println(arrays.tostring(old); 50. system.out.println(arrays.tostring(strings); 51. 52. numberold=getrundom(50); 53. integeroo=1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21; 54. old=oo; 55. for(strings:strings) 56. numbertestnum=arrays.copyof(old,old.length); 57. longbegin=system.currenttimemillis(); 58. sorttest.class.getmethod(s,number.class).invoke(this,(object)testnum); 59. 60. longend=system.currenttimemillis(); 61. system.out.println(s+:+(end-begin)+t); 62. system.out.println(arrays.tostring(testnum); 63. 64. system.out.println(); 65. 66. 67. 68. 69. privatevoidtest(stringstrings,longbegin,longend,longstep)throwsexception 70. system.out.print(数量t); 71. for(stringstr:strings) 72. system.out.print(str+t); 73. 74. system.out.println(); 75. for(longi=begin;iend;i=i+step) 76. system.out.print(i+个t); 77. numberold=getrundom(i); 78. for(strings:strings) 79. numbertestnum=arrays.copyof(old,old.length); 80. longbegintime=system.currenttimemillis(); 81. sorttest.class.getmethod(s,number.class).invoke(this,(object)testnum); 82. 83. longendtime=system.currenttimemillis(); 84. system.out.print(endtime-begintime)+t); 85. /system.out.println(arrays.tostring(testnum); 86. 87. system.out.println(); 88. 89. 90. 91. 92. privatestaticintegergetrundom(longnum) 93. listlist=newarraylist(); 94. for(longi=0;i0.5) 97. k=(int)(math.random()*integer.max_value); 98. else 99. k=(int)(math.random()*integer.min_value); 100. 101. list.add(k); 102. 103. returnlist.toarray(newintegerlist.size(); 104. 105. 106. 107. 108. 109. /* 110. *插入排序直接插入排序 111. *paramdata 112. */113. publicstaticvoid直接插入排序(numberdata) 114. 115. numbertmp=null; 116. 117. for(inti=1;i=0&tmp.doublevalue()dataj.doublevalue() 121. dataj+1=dataj; 122. j-; 123. 124. dataj+1=tmp; 125. 126. 127. /* 128. *插入排序折半插入排序 129. *paramdata 130. */131. publicstaticvoid折半插入排序(numberdata) 132. 133. numbertmp=null; 134. for(inti=1;i=smallpoint) 140. intmid=(smallpoint+bigpoint)/2; 141. if(tmp.doublevalue()datamid.doublevalue() 142. smallpoint=mid+1; 143. else 144. bigpoint=mid-1; 145. 146. 147. for(intj=i;jsmallpoint;j-) 148. dataj=dataj-1; 149. 150. databigpoint+1=tmp; 151. 152. 153. 154. /* 155. *插入排序希尔排序 156. *paramdata 157. */158. publicstaticvoid希尔排序(numberdata) 159. 160. intspan=data.length/7; 161. if(span=0)span=1; 162. while(span=1) 163. for(inti=0;ispan;i+) 164. for(intj=i;j=0&datap.doublevalue()temp.doublevalue() 169. datap+span=datap; 170. p-=span; 171. 172. datap+span=temp; 173. 174. 175. span=span/2; 176. 177. 178. 179. 180. 181. /* 182. *交换排序冒泡排序 183. * 184. *paramdata 185. */186. publicstaticvoid冒泡排序(numberdata) 187. 188. for(inti=0;idata.length;i+) 189. /将相邻两个数进行比较，较大的数往后冒泡 190. for(intj=0;jdataj+1.doublevalue() 192. /交换相邻两个数 193. swap(data,j,j+1); 194. 195. 196. 197. 198. /* 199. *交换排序快速排序 200. *paramdata 201. */202. publicstaticvoid快速排序(numberdata) 203. 204. quicksort(data,0,data.length-1); 205. 206. 207. privatestaticvoidquicksort(numberdata,intbegin,intend) 208. /system.out.println(begin+:+end); 209. if(beginend) 210. /取中点 211. intmid=(begin+end)/2; 212. if(dataend.doublevalue()databegin.doublevalue() 213. swap(data,end,begin); 214. 215. if(dataend.doublevalue()datamid.doublevalue() 216. swap(data,end,mid); 217. 218. if(datamid.doublevalue()databegin.doublevalue() 219. swap(data,mid,begin); 220. 221. 222. swap(data,mid,begin); 223. 224. /system.out.println(arrays.tostring(arrays.copyofrange(data,begin,end); 225. intmin=begin+1; 226. intbig=end; 227. 228. while(true) 229. while(minbig&datamin.doublevalue()databegin.doublevalue()min+; 230. while(min=databegin.doublevalue()big-; 231. if(min=big) 232. break; 233. 234. swap(data,min,big); 235. 236. if(databegin.doublevalue()datamin.doublevalue() 237. swap(data,begin,min); 238. 239. 240. if(min1) 241. quicksort(data,begin,min-1); 242. /if(minend) 243. quicksort(data,min,end); 244. 245. 246. /* 247. *选择排序简单选择排序 248. *paramdata 249. */250. publicstaticvoid简单选择排序(numberdata) 251. 252. for(inti=0;idata.length-1;i+) 253. intsmallpoint=i; 254. for(intj=i+1;jdataj.doublevalue() 256. smallpoint=j; 257. 258. 259. swap(data,i,smallpoint); 260. 261. 262. 263. 264. /* 265. *选择排序堆排序 266. *paramdata 267. */268. publicstaticvoid堆排序(numberdata) 269. 270. 271. intn=data.length; 272. for(inti=n/2;i=0;i-) 273. keepheap(data,n,i); 274. 275. while(n0) 276. swap(data,0,n-1); 277. keepheap(data,-n,0); 278. 279. 280. 281. 282. privatestaticvoidkeepheap(numbera,intn,inti) 283. numberx=ai; 284. intj=2*i+1; 285. while(j=n-1) 286. if(jn-1&aj.doublevalue()x.doublevalue() 289. ai=aj; 290. i=j; 291. j=2*i; 292. else 293. break; 294. 295. 296. ai=x; 297. 298. 299. 300. 301. 302. /* 303. *归并排序法归并排序 304. *paramdata 305. */306. publicstaticvoid归并排序(numberdata) 307. 308. numberresult=merge_sort(data,0,data.length-1); 309. for(inti=0;iresult.length;i+) 310. datai=resulti; 311. 312. 313. privatestaticnumbermerge_sort(numberarray,intstart,intend) 314. numberresult=newnumberend-start+1; 315. if(startend) 316. intmid=(start+end)/2; 317. numberleft=merge_sort(array,start,mid