2025-02-17

package com.stig_dim.hello; 

02   

03 import java.util.Random; 

04   

05 public class TestSorts { 

06   

07     /** 

08      * @param null; 

09      * @author Administrator 

10      * @category 測試主流幾大排序算法的效率 

11      * @see <<算法導論1-3章>> 

12      */

13     @SuppressWarnings("deprecation") 

14     public static void main(String[] args) { 

15         int[] testarr = new int[4086]; 

16         double t; 

17         InsertData2Array(testarr); 

18   

19         t = System.currentTimeMillis(); 

20         SortAlgorithem.BubbleSort(testarr); 

21         t = System.currentTimeMillis() – t; 

22         for (int num : testarr) 

23             System.out.print(num + " "); 

24         System.out.println("冒泡排序所花時間為:" + t + "ms"); 

25   

26         t = System.currentTimeMillis(); 

27         SortAlgorithem.InsertSort(testarr); 

28         t = System.currentTimeMillis() – t; 

29         for (int num : testarr) 

30             System.out.print(num + " "); 

31         System.out.println("插入排序所花時間為:" + t + "ms"); 

32   

33         t = System.currentTimeMillis(); 

34         SortAlgorithem.MergeSort(testarr); 

35         t = System.currentTimeMillis() – t; 

36         for (int num : testarr) 

37             System.out.print(num + " "); 

38         System.out.println("並歸(非分治版)排序所花時間為:" + t + "ms"); 

39     } 

40   

41     private static void InsertData2Array(int[] a) { 

42   

43         Random rd = new Random(System.currentTimeMillis()); 

44         for (int i = 0; ++i < a.length;) { 

45             a[i] = rd.nextInt(30); 

46             System.out.print(a[i] + " "); 

47         } 

48         System.out.println("原始數據"); 

49     } 

50 }


view sourceprint?01 package com.stig_dim.hello; 

02   

03 /** 

04  * @author Administrator 

05  * @category 所有輸入N為4086 模擬平均情況 

06  */

07 public class SortAlgorithem { 

08     /** 

09      * @deprecated 無腦冒泡 增長率 = ∑(O(n^2)) 

10      * */

11     public static void BubbleSort(int[] a) { 

12         for(int i = a.length;–i>0;){ 

13             for(int j = 0;j < i;j++) 

14             { 

15                 if(a[j] > a[j+1])  

16                 { 

17                     int temp = a[j]; 

18                     a[j] = a[j+1]; 

19                     a[j+1] = temp; 

20                 } 

21             } 

22         } 

23     } 

24       

25     /** 

26      * @category see <算法導論>第一章 

27      * @deprecated  

28      * @deprecated 插入排序 增長率 = O(n^2) 

29      * 雖是插入排序 其實質還是冒泡,隻是冒的"泡"每一次大小不一樣  

30      */

31     public static void InsertSort(int[] a) { 

32         for (int i = 1; i < a.length; i++) { 

33             int N = a[i];// 右手抽起牌N 

34             int j; 

35             for (j = i – 1; j >= 0 && a[j]>=N; j–)//找位置 

36                 a[j + 1] = a[j];//左手洗牌騰位置 

37             a[j + 1] = N; //插入牌N到左手已經排好的牌面中  

38         } 

39     } 

40       

41       

42     /** 

43      * @category = 並歸排序(無遞歸非分治) 增長率 = O(n) 

44      * */

45     public static void MergeSort(int [] a){ 

46         //pided? do it ~ [ A[] -> [[ A[1..p] + A[r-p+1] ]] ]  

47         int N = a.length; 

48         int [] L = new int[N/2];//p   //漂亮的把戲 用RAM換時間.. 

49         int [] R = new int[(N-N/2)];//q //此為比較排序系列中的平均最差時間最低 但不及堆排序等其他系列 

50         for(int i = 0 ; i < L.length; i++) //輸入足夠大 情況越復雜 快速排序優勢越明顯 線性表現一般 平均表現卻很好 

51             L[i] = a[i]; 

52         for(int i = 0; i < R.length;i++) 

53             R[i] = a[i]; 

54           

55         for(int i = 0,j = 0;i < L.length&&j<R.length; i++){ 

56             if(L[i] < R[j]){ 

57                 a[i] = L[i]; 

58                 ++i; 

59             }else

60             { 

61                 a[i] = R[j]; 

62                 ++j; 

63             } 

64         } 

65     } 

66 }

運行截圖

作者“美女你的磚頭掉瞭的博客”
 

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *