<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        


    


    大魚
    

    

    




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

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

    

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

    1、冒泡排序
    

    2、簡單選擇排序
    

    3、直接插入排序
    

    4、折半插入排序
    

    5、希爾排序
    

    6、堆排序
    

    7、歸并排序
    

    8、快速排序
    

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

    

    

    直接上圖：單位毫秒
    

    

    


    


    數(shù)量
    		


    冒泡排序
    		


    簡單選擇排序
    		


    直接插入排序
    		


    折半插入排序
    		


    希爾排序
    		


    堆排序
    		


    歸并排序
    		


    快速排序
    

    


    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. * 選擇排序:簡單選擇排序和堆排序 
    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. * 簡單選擇排序 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[]{"冒泡排序","簡單選擇排序","直接插入排序","折半插入排序","系爾排序","堆排序","歸并排序","快速排序"}; 
    36. //new SortTest().testErr(testErr); 
    38. //排序1（全部） 
    39. String[] strs=new String[]{"冒泡排序","簡單選擇排序","直接插入排序","折半插入排序","希爾排序","堆排序","歸并排序","快速排序"}; 
    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. * 選擇排序————簡單選擇排序 
    248. * @param data 
    249. */ 
    250. public static void 簡單選擇排序(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 大魚 閱讀(833) 評(píng)論(1)  編輯  收藏  所屬分類: 軟件工程 
		
    
	
    
	
	





    
	    
    


    

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

    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
高潮内射免费看片|
亚洲伊人久久大香线蕉综合图片|
亚洲国产精品免费观看|
国产电影午夜成年免费视频|
97se亚洲综合在线|
亚洲电影在线免费观看|
精品亚洲成AV人在线观看|
久久综合国产乱子伦精品免费|
亚洲AV日韩AV永久无码久久|
毛片在线全部免费观看|
亚洲AV日韩精品久久久久久|
99热这里只有精品6免费|
久久国产亚洲高清观看|
色影音免费色资源|
亚洲一卡2卡三卡4卡无卡下载|
国内自产少妇自拍区免费|
大桥未久亚洲无av码在线|
免费人成网站在线播放|
国产A∨免费精品视频|
亚洲午夜无码久久久久|
99久久国产精品免费一区二区
|
丁香花在线视频观看免费|
日本亚洲视频在线|
久久精品一本到99热免费|
jlzzjlzz亚洲jzjzjz|
夭天干天天做天天免费看|
久久精品国产亚洲AV|
亚洲午夜无码AV毛片久久|
两个人看的www视频免费完整版|
国产精品亚洲一区二区三区在线|
免费无码VA一区二区三区|
亚洲人成免费网站|
色吊丝最新永久免费观看网站|
美女被免费视频网站|
亚洲色精品aⅴ一区区三区|
久久精品免费视频观看|
亚洲综合色区中文字幕|
国产三级免费观看|
a级毛片黄免费a级毛片|
亚洲系列中文字幕|
成人au免费视频影院|