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 //divided 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 56 if(L[i] < R[j]){ 57 a[i] = L[i]; 58