大魚
          

          

          




          
	
					
	
          
		
          
			排序算法java版，速度排行：冒泡排序、簡(jiǎn)單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序  
		
          
		
          先推薦一篇關(guān)于排序算法的文章：http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html
          

          本文思路部分來(lái)源于上篇文章，但測(cè)得的結(jié)果似乎不大相同，不知是因?yàn)閖ava的緣故還是因?yàn)槲宜惴ǖ木壒剩瑲g迎拍磚。
          

          

          復(fù)習(xí)排序，順便比下各種算法的速度，榜單如下：
          

          1、冒泡排序
          

          2、簡(jiǎn)單選擇排序
          

          3、直接插入排序
          

          4、折半插入排序
          

          5、希爾排序
          

          6、堆排序
          

          7、歸并排序
          

          8、快速排序
          

          當(dāng)然這是慢速排行，哈哈~~
          

          

          

          直接上圖：?jiǎn)挝缓撩?/p>

          

          


          


          數(shù)量
          		


          冒泡排序
          		


          簡(jiǎn)單選擇排序
          		


          直接插入排序
          		


          折半插入排序
          		


          希爾排序
          		


          堆排序
          		


          歸并排序
          		


          快速排序
          

          


          10000個(gè)
          		


          1578
          		


          1250
          		


          672
          		


          250
          		


          0
          		


          15
          		


          16
          		


          0
          

          


          15000個(gè)
          		


          3453
          		


          2765
          		


          1563
          		


          531
          		


          16
          		


          15
          		


          16
          		


          0
          

          


          20000個(gè)
          		


          6140
          		


          4547
          		


          2453
          		


          828
          		


          16
          		


          16
          		


          15
          		


          16
          

          


          25000個(gè)
          		


          10079
          		


          7171
          		


          3969
          		


          1313
          		


          31
          		


          16
          		


          15
          		


          16
          

          


          30000個(gè)
          		


          14641
          		


          10313
          		


          5578
          		


          1906
          		


          31
          		


          31
          		


          16
          		


          31
          

          


          35000個(gè)
          		


          20141
          		


          14328
          		


          7890
          		


          2563
          		


          31
          		


          31
          		


          32
          		


          15
          

          


          40000個(gè)
          		


          25766
          		


          18359
          		


          10094
          		


          3422
          		


          47
          		


          31
          		


          31
          		


          32
          

          


          45000個(gè)
          		


          32469
          		


          24063
          		


          13062
          		


          4359
          		


          47
          		


          47
          		


          31
          		


          47
          

          

          

          

          由于"希爾排序","堆排序","歸并排序","快速排序"太快，以至于在上圖幾乎是條直線，故有了下面轉(zhuǎn)為他們準(zhǔn)備的加強(qiáng)版
          

          

          


          


          數(shù)量
          		


          希爾排序
          		


          堆排序
          		


          歸并排序
          		


          快速排序
          

          


          100000個(gè)
          		


          172
          		


          140
          		


          110
          		


          93
          

          


          200000個(gè)
          		


          469
          		


          406
          		


          235
          		


          234
          

          


          300000個(gè)
          		


          812
          		


          703
          		


          422
          		


          375
          

          


          400000個(gè)
          		


          1125
          		


          1031
          		


          516
          		


          531
          

          


          500000個(gè)
          		


          1406
          		


          1282
          		


          719
          		


          656
          

          


          600000個(gè)
          		


          1828
          		


          1703
          		


          860
          		


          859
          

          


          700000個(gè)
          		


          2531
          		


          2063
          		


          1000
          		


          968
          

          


          800000個(gè)
          		


          2735
          		


          2453
          		


          1140
          		


          1188
          

          


          900000個(gè)
          		


          3047
          		


          2843
          		


          1391
          		


          1266
          

          


          1000000個(gè)
          		


          3375
          		


          3187
          		


          1516
          		


          1422
          

          


          1100000個(gè)
          		


          3922
          		


          3500
          		


          1625
          		


          1609
          

          


          1200000個(gè)
          		


          4421
          		


          3954
          		


          1969
          		


          1812
          

          


          1300000個(gè)
          		


          4797
          		


          4422
          		


          2000
          		


          1953
          

          


          1400000個(gè)
          		


          5391
          		


          4797
          		


          2547
          		


          2094
          

          


          1500000個(gè)
          		


          5437
          		


          5219
          		


          2625
          		


          2328
          

          


          1600000個(gè)
          		


          6203
          		


          5546
          		


          2469
          		


          2485
          

          


          1700000個(gè)
          		


          6532
          		


          5953
          		


          2844
          		


          2672
          

          


          1800000個(gè)
          		


          7125
          		


          6421
          		


          2984
          		


          2844
          

          

          

          補(bǔ)上代碼：
          

          

          

          

          Java代碼  收藏代碼
          

          1. import java.util.ArrayList; 
          2. import java.util.Arrays; 
          3. import java.util.List; 
          5. /** 
          6. * 插入排序:直接插入排序、折半插入排序和系爾排序 
          7. * 交換排序:冒泡排序和快速排序 
          8. * 選擇排序:簡(jiǎn)單選擇排序和堆排序 
          9. * 歸并排序:歸并排序 
          10. * 
          11. * 基本思想 
          12. * 插入排序:將第N個(gè)記錄插入到前面(N-1)個(gè)有序的記錄當(dāng)中。 
          13. * 交換排序:按照某種順序比較兩個(gè)記錄的關(guān)鍵字大小，然后根據(jù)需要交換兩個(gè)記錄的位置。 
          14. * 選擇排序:根據(jù)某種方法選擇一個(gè)關(guān)鍵字最大的記錄或者關(guān)鍵字最小的記錄，放到適當(dāng)?shù)奈恢谩?/span> 
          15. * 
          16. * 排序方法比較 
          17. * 排序方法 平均時(shí)間 最壞時(shí)間 輔助存儲(chǔ) 
          18. * 直接插入排序 O(N2) O(N2) O(1) 
          19. * 起泡排序 O(N2) O(N2) O(1) 
          20. * 快速排序 O(Nlog2N) O(N2) O(Nlog2N) 
          21. * 簡(jiǎn)單選擇排序 O(N2) O(N2) O(1) 
          22. * 堆排序 O(Nlog2N) O(Nlog2N) O(1) 
          23. * 歸并排序 O(Nlog2N) O(Nlog2N) O(n) 
          24. * 基數(shù)排序 O(d(n+radix)) O(d(n+radix)) O(radix) 
          25. * 
          26. * 
          27. * 
          28. * @author Administrator 
          29. * 
          30. */ 
          31. public class SortTest { 
          33. public static void main(String[] args)throws Exception { 
          34. //測(cè)試排序是否正確 
          35. //String[] testErr=new String[]{"冒泡排序","簡(jiǎn)單選擇排序","直接插入排序","折半插入排序","系爾排序","堆排序","歸并排序","快速排序"}; 
          36. //new SortTest().testErr(testErr); 
          38. //排序1（全部） 
          39. String[] strs=new String[]{"冒泡排序","簡(jiǎn)單選擇排序","直接插入排序","折半插入排序","希爾排序","堆排序","歸并排序","快速排序"}; 
          40. new SortTest().test(strs,10000,50000,5000); 
          42. //排序2（加強(qiáng)） 
          43. String[] strs2=new String[]{"希爾排序","堆排序","歸并排序","快速排序"}; 
          44. new SortTest().test(strs2,100000,1900000,100000); 
          46. } 
          47. private void testErr(String[] strings) throws Exception{ 
          49. //System.out.println(Arrays.toString(old)); 
          50. System.out.println(Arrays.toString(strings)); 
          52. Number[] old=getRundom(50); 
          53. Integer[] oo={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(String s:strings){ 
          56. Number[] testNum=Arrays.copyOf(old, old.length); 
          57. long begin=System.currentTimeMillis(); 
          58. SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum); 
          60. long end=System.currentTimeMillis(); 
          61. System.out.println(s+":"+(end-begin)+"\t"); 
          62. System.out.println(Arrays.toString(testNum)); 
          63. } 
          64. System.out.println(); 
          67. } 
          69. private void test(String[] strings,long begin,long end,long step) throws Exception{ 
          70. System.out.print("數(shù)量\t"); 
          71. for(String str:strings){ 
          72. System.out.print(str+"\t"); 
          73. } 
          74. System.out.println(); 
          75. for(long i=begin;i<end;i=i+step){ 
          76. System.out.print(i+"個(gè)\t"); 
          77. Number[] old=getRundom(i); 
          78. for(String s:strings){ 
          79. Number[] testNum=Arrays.copyOf(old, old.length); 
          80. long beginTime=System.currentTimeMillis(); 
          81. SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum); 
          83. long endTime=System.currentTimeMillis(); 
          84. System.out.print((endTime-beginTime)+"\t"); 
          85. //System.out.println(Arrays.toString(testNum)); 
          86. } 
          87. System.out.println(); 
          88. } 
          90. } 
          92. private static Integer[] getRundom(long num) { 
          93. List<Integer> list=new ArrayList<Integer>(); 
          94. for(long i=0;i<num;i++){ 
          95. int k; 
          96. if(Math.random()>0.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. return list.toArray(new Integer[list.size()]); 
          104. } 
          109. /** 
          110. * 插入排序————直接插入排序 
          111. * @param data 
          112. */ 
          113. public static void 直接插入排序(Number[] data) 
          114. { 
          115. Number tmp=null ; 
          117. for(int i=1;i<data.length;i++){ 
          118. tmp = data[i]; 
          119. int j=i-1; 
          120. while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){ 
          121. data[j+1]=data[j]; 
          122. j--; 
          123. } 
          124. data[j+1]=tmp; 
          125. } 
          126. } 
          127. /** 
          128. * 插入排序————折半插入排序 
          129. * @param data 
          130. */ 
          131. public static void 折半插入排序(Number[] data) 
          132. { 
          133. Number tmp=null ; 
          134. for(int i=1;i<data.length;i++){ 
          135. tmp = data[i]; 
          136. int smallpoint=0; 
          137. int bigpoint=i-1; 
          139. while(bigpoint>=smallpoint){ 
          140. int mid=(smallpoint+bigpoint)/2; 
          141. if(tmp.doubleValue()>data[mid].doubleValue()){ 
          142. smallpoint=mid+1; 
          143. }else{ 
          144. bigpoint=mid-1; 
          145. } 
          146. } 
          147. for(int j=i;j>smallpoint;j--){ 
          148. data[j]=data[j-1]; 
          149. } 
          150. data[bigpoint+1]=tmp; 
          151. } 
          152. } 
          154. /** 
          155. * 插入排序————希爾排序 
          156. * @param data 
          157. */ 
          158. public static void 希爾排序(Number[] data) 
          159. { 
          160. int span=data.length/7; 
          161. if(span==0)span=1; 
          162. while(span>=1){ 
          163. for(int i=0;i<span;i++){ 
          164. for(int j=i;j<data.length;j=j+span){ 
          165. //組內(nèi)直接插入排序 
          166. int p = j-span; 
          167. Number temp = data[j]; 
          168. while( p >=0 && data[p].doubleValue() > temp.doubleValue()){ 
          169. data[p+span] = data[p]; 
          170. p -=span; 
          171. } 
          172. data[p + span] = temp; 
          173. } 
          174. } 
          175. span=span/2; 
          176. } 
          179. } 
          181. /** 
          182. * 交換排序————冒泡排序 
          183. * 
          184. * @param data 
          185. */ 
          186. public static void 冒泡排序(Number[] data) 
          187. { 
          188. for (int i = 0; i < data.length; i++) { 
          189. //將相鄰兩個(gè)數(shù)進(jìn)行比較，較大的數(shù)往后冒泡 
          190. for (int j = 0; j < data.length - i-1; j++) { 
          191. if (data[j].doubleValue()> data[j + 1].doubleValue()) { 
          192. //交換相鄰兩個(gè)數(shù) 
          193. swap(data, j, j + 1); 
          194. } 
          195. } 
          196. } 
          197. } 
          198. /** 
          199. * 交換排序————快速排序 
          200. * @param data 
          201. */ 
          202. public static void 快速排序(Number[] data) 
          203. { 
          204. QuickSort(data,0,data.length-1); 
          205. } 
          207. private static void QuickSort(Number[] data, int begin, int end) { 
          208. // System.out.println(begin+":"+end); 
          209. if(begin<end){ 
          210. //取中點(diǎn) 
          211. int mid=(begin+end)/2; 
          212. if(data[end].doubleValue()<data[begin].doubleValue()){ 
          213. swap(data, end, begin); 
          214. } 
          215. if(data[end].doubleValue()<data[mid].doubleValue()){ 
          216. swap(data, end, mid); 
          217. } 
          218. if(data[mid].doubleValue()<data[begin].doubleValue()){ 
          219. swap(data, mid, begin); 
          220. } 
          222. swap(data, mid, begin); 
          224. // System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) ); 
          225. int min=begin+1; 
          226. int big=end; 
          228. while(true){ 
          229. while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;} 
          230. while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;} 
          231. if(min>=big){ 
          232. break; 
          233. } 
          234. swap(data, min, big); 
          235. } 
          236. if(data[begin].doubleValue()>data[min].doubleValue()){ 
          237. swap(data, begin, min); 
          238. } 
          240. if(min>1) 
          241. QuickSort(data,begin,min-1); 
          242. //if(min<end) 
          243. QuickSort(data,min,end); 
          244. } 
          245. } 
          246. /** 
          247. * 選擇排序————簡(jiǎn)單選擇排序 
          248. * @param data 
          249. */ 
          250. public static void 簡(jiǎn)單選擇排序(Number[] data) 
          251. { 
          252. for (int i = 0; i < data.length-1; i++) { 
          253. int smallPoint=i; 
          254. for (int j = i+1; j < data.length; j++) { 
          255. if (data[smallPoint].doubleValue()> data[j].doubleValue()) { 
          256. smallPoint=j; 
          257. } 
          258. } 
          259. swap(data, i, smallPoint); 
          260. } 
          262. } 
          264. /** 
          265. * 選擇排序————堆排序 
          266. * @param data 
          267. */ 
          268. public static void 堆排序(Number[] data) 
          269. { 
          271. int n = data.length; 
          272. for(int i=n/2;i>=0;i--){ 
          273. keepHeap(data, n, i); 
          274. } 
          275. while (n > 0) { 
          276. swap(data, 0, n-1); 
          277. keepHeap(data, --n, 0); 
          278. } 
          279. } 
          282. private static void keepHeap(Number[] a, int n, int i) { 
          283. Number x = a[i]; 
          284. int j = 2 * i + 1; 
          285. while (j <= n - 1) { 
          286. if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue()) 
          287. ++j; 
          288. if (a[j].doubleValue() > x.doubleValue()) { 
          289. a[i] = a[j]; 
          290. i = j; 
          291. j = 2 * i ; 
          292. } else{ 
          293. break; 
          294. } 
          295. } 
          296. a[i] = x; 
          297. } 
          302. /** 
          303. * 歸并排序法————歸并排序 
          304. * @param data 
          305. */ 
          306. public static void 歸并排序(Number[] data) 
          307. { 
          308. Number[] result = merge_sort(data,0,data.length-1); 
          309. for(int i=0;i<result.length;i++){ 
          310. data[i]=result[i]; 
          311. } 
          312. } 
          313. private static Number[] merge_sort(Number[] array, int start, int end){ 
          314. Number[] result = new Number[end-start+1]; 
          315. if(start< end){ 
          316. int mid= (start+end)/2; 
          317. Number[] left= merge_sort(array, start, mid); 
          318. Number[] right = merge_sort(array, mid+1, end); 
          319. result= merge(left,right); 
          320. } else if (start == end) { 
          321. result[0] = array[start]; 
          322. return result; 
          323. } 
          324. return result; 
          325. } 
          326. private static Number[] merge(Number[] left, Number[] right) { 
          327. Number[] result = new Number[left.length+right.length]; 
          328. int i=0; 
          329. int j=0; 
          330. int k=0; 
          331. while(i< left.length&&j< right.length){ 
          332. if(left[i].doubleValue()< right[j].doubleValue()){ 
          333. result[k++] = left[i++]; 
          334. }else{ 
          335. result[k++] = right[j++]; 
          337. } 
          338. } 
          339. while(i< left.length){ 
          340. result[k++] = left[i++]; 
          341. } 
          342. while (j< right.length) { 
          343. result[k++]= right[j++]; 
          344. } 
          345. return result; 
          346. } 
          348. /** 
          349. * 交換數(shù)組中指定的兩元素的位置 
          350. * @param data 
          351. * @param x 
          352. * @param y 
          353. */ 
          354. private static void swap(Number[] data, int x, int y) { 
          355. Number temp = data[x]; 
          356. data[x] = data[y]; 
          357. data[y] = temp; 
          358. } 
          359. }
          
		
          
			posted on 2011-10-06 23:34 大魚 閱讀(835) 評(píng)論(1)  編輯  收藏  所屬分類: 軟件工程 
		
          
	
          
	
	





          
	    
    


          

          評(píng)論
          
	
	
			
          
				# re: 排序算法java版，速度排行：冒泡排序、簡(jiǎn)單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序  
					
						2011-10-07 19:35
					
				安多
			
          
			
          
				收藏了  回復(fù)  更多評(píng)論
				  
			
          
		

          




          








          

				

          



    







          
        
	




主站蜘蛛池模板：
石屏县|
涪陵区|
普安县|
方山县|
长岛县|
永清县|
遂平县|
云南省|
通榆县|
浮梁县|
长武县|
西峡县|
宜都市|
新田县|
衡阳县|
大英县|
荆州市|
抚顺县|
福安市|
甘南县|
陵水|
石首市|
大同市|
木里|
利川市|
曲沃县|
景宁|
通许县|
乐平市|
呈贡县|
锡林浩特市|
奈曼旗|
老河口市|
双鸭山市|
广德县|
长兴县|
苍溪县|
筠连县|
卓尼县|
贵州省|
留坝县|