冒泡排序、簡單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序

1、排序算法java版，速度排行：冒泡排序、簡單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序文章分類:java編程 先推薦一篇關于排序算法的文章：本文思路部分來源于上篇文章，但測得的結(jié)果似乎不大相同，不知是因為java的緣故還是因為我算法的緣故，歡迎拍磚。復習排序，順便比下各種算法的速度，榜單如下：1、冒泡排序2、簡單選擇排序3、直接插入排序4、折半插入排序5、希爾排序6、堆排序7、歸并排序8、快速排序當然這是慢速排行，哈哈直接上圖：單位毫秒數(shù)量冒泡排序簡單選擇排序直接插入排序折半插入排序希爾排序堆排序歸并排序快速排序10000個1578125067225001516

2、015000個345327651563531161516020000個6140454724538281616151625000個100797171396913133116151630000個1464110313557819063131163135000個2014114328789025633131321540000個25766183591009434224731313245000個324692406313062435947473147由于希爾排序,堆排序,歸并排序,快速排序太快，以至于在上圖幾乎是條直線，故有了下面轉(zhuǎn)為他們準備的加強版數(shù)量希爾排序堆排序歸并排序快速排序100000個172140

3、11093200000個469406235234300000個812703422375400000個11251031516531500000個14061282719656600000個18281703860859700000個253120631000968800000個2735245311401188900000個30472843139112661000000個33753187151614221100000個39223500162516091200000個44213954196918121300000個47974422200019531400000個5391479725472094150000

4、0個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. *插入排序:

5、將第n個記錄插入到前面(n-1)個有序的記錄當中。 13. *交換排序:按照某種順序比較兩個記錄的關鍵字大小，然后根據(jù)需要交換兩個記錄的位置。 14. *選擇排序:根據(jù)某種方法選擇一個關鍵字最大的記錄或者關鍵字最小的記錄，放到適當?shù)奈恢谩?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)

6、23. *歸并排序o(nlog2n)o(nlog2n)o(n) 24. *基數(shù)排序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.

7、 /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. priva

8、tevoidtesterr(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; 5

9、5. 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(

10、arrays.tostring(testnum); 63. 64. system.out.println(); 65. 66. 67. 68. 69. privatevoidtest(stringstrings,longbegin,longend,longstep)throwsexception 70. system.out.print(數(shù)量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.

11、 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.

12、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)(mat

13、h.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.doublev

14、alue() 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

15、. 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; 16

16、2. 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冒泡排序(num

17、berdata) 187. 188. for(inti=0;idata.length;i+) 189. /將相鄰兩個數(shù)進行比較，較大的數(shù)往后冒泡 190. for(intj=0;jdataj+1.doublevalue() 192. /交換相鄰兩個數(shù) 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.

18、 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.

19、 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(minb

20、ig&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); 2

21、42. /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,smallpoin

22、t); 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. privatestaticvoi

23、dkeepheap(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歸并排序

24、(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); 318