Insertion Sort 与 Merge Sort的性能比较(Java)

蔚落 2022-01-12 08:57 153阅读 0赞

1 　　 public static void main(String[] args)
     2     {
     3         Scanner input = new Scanner(System.in);
     4         int n = input.nextInt();
     5         int[] a = new int[n];
     6         
     7         //生成n个随机数
     8         for(int i = 0; i < n; i++)
     9             a[i] = (int)(Math.random() * 100);
    10         
    11         /*long start = System.currentTimeMillis();
    12         InsertionSort(a);
    13         long end = System.currentTimeMillis();*/
    14         //100000个测试数据InsertionSort的排序时间约为2800ms
    15             
    16         /*System.out.println(Arrays.toString(a));
    17         System.out.println(start);
    18         System.out.println(end);
    19         System.out.printf("The time is: %d", end - start);*/
    20         
    21         //获取当前时间(ms)
    22         long start = System.currentTimeMillis();
    23         divide(a, 0, a.length - 1);
    24         long end = System.currentTimeMillis();
    25         //100000000个测试数据MergeSort的排序时间约为12000ms 10000000个测试数据用时约为1200ms
    26         //相对于平均时间复杂度O(n^2)的插入排序 随着测试数据数量级的增长 性能提升极大
    27         
    28         //System.out.println(Arrays.toString(a));
    29         System.out.println(start);
    30         System.out.println(end);
    31         // end - start 即为排序算法运行的时间
    32         System.out.println("The time is: " + (end - start));
    33     }
    34     
    35     /*public static void InsertionSort(int[] a)
    36     {
    37         for(int i = 1; i < a.length; i++)
    38         {
    39             int key = a[i];
    40             int j;
    41             for(j = i - 1; j >= 0 && key < a[j]; j--)
    42                 a[j + 1] = a[j];
    43             a[j + 1] = key;
    44         }
    45     }*/
    46     
    47     public static void divide(int[] a, int front, int rear)
    48     {
    49         if(rear <= front)
    50             return;
    51         
    52         int mid = front + (rear - front) / 2;
    53         divide(a, mid + 1, rear);
    54         divide(a, front, mid);
    55         merge(a, front, mid, rear);
    56     }
    57     
    58     public static void merge(int[] a, int front, int mid, int rear)
    59     {
    60         int[] b = new int[rear - front + 1];
    61         int i = front, j = mid + 1, k = 0;
    62         
    63         while(i <= mid && j <= rear)
    64             if(a[i] < a[j])
    65                 b[k++] = a[i++];
    66             else
    67                 b[k++] = a[j++];
    68         
    69         if(i > mid)
    70             while(j <= rear)
    71                 b[k++] = a[j++];
    72         else
    73             while(i <= mid)
    74                 b[k++] = a[i++];
    75         
    76         for(int t = 0, q = front; t < b.length; t++, ++q)
    77             a[q] = b[t];
    78     }

转载于:https://www.cnblogs.com/Huayra/p/10513431.html