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 }
作者“美女你的磚頭掉瞭的博客”