[Day19] CH10：排序大家族——实验

咦？怎麽还是排序呢？没错！经过前四天的学习，我们今天要来做一个小实验，比较各个排序演算法在相同巨量数据下的排序速度，虽然时间复杂度相同，但他们还是有快慢之分的，究竟谁是最後的赢家呢？我们就来实际做实验吧！

既然是实验，那麽给定的参数值就要一样才能比较，我们需要大量且相同的资料当作要排序的阵列元素，这时候就可以使用「随机数字」这个方法，在 Java 中有 Math 函式库里的 random 方法和 java.util 里的 Random 方法，两种用法不太一样，这里要介绍的是第二种方法：

//产生一个 Random 物件，并设定乱树种子为 2
Random r = new Random(2);

除此之外，我们还需要能测量执行时间的方法，这里要介绍的是 currentTimeMillis()：

long start = System.currentTimeMillis();    //开始时间
//执行程序
long duration = System.currentTimeMillis() - start;  //现在时间 - 开始时间 ms

有了以上两种方法，搭配前四天教的内容，大家应该可以尝试自己写写看，以下示范历程序码：

import java.util.Random;

public class SortExperiment {
    public static void main(String[] args){
        int i;
        int[] arr1 = new int[100000];
        int[] arr2 = new int[100000];
        int[] arr3 = new int[100000];
        int[] arr4 = new int[100000];

        Random r = new Random(1);   //设定乱树种子为 1

        //给予四阵列相同的实验数值
        for(i = 0 ; i < 100000 ; i++){
            arr1[i] = r.nextInt();
            arr2[i] = arr1[i];
            arr3[i] = arr1[i];
            arr4[i] = arr1[i];
        }

        long start, duration; //开始时间、执行时间
        start = System.currentTimeMillis();
        bubblesort(arr1);
        duration = System.currentTimeMillis() - start;  //现在时间 - 开始时间
        System.out.println("Execution time of bubble sort: " + duration + " ms");

        start = System.currentTimeMillis();
        selectionsort(arr2);
        duration = System.currentTimeMillis() - start;  //现在时间 - 开始时间
        System.out.println("Execution time of selection sort: " + duration + " ms");

        start = System.currentTimeMillis();
        insertionsort(arr3);
        duration = System.currentTimeMillis() - start;  //现在时间 - 开始时间
        System.out.println("Execution time of insertion sort: " + duration + " ms");

        start = System.currentTimeMillis();
        mergesort(arr4, 0, arr4.length-1);
        duration = System.currentTimeMillis() - start;  //现在时间 - 开始时间
        System.out.println("Execution time of merge sort: " + duration + " ms");
    }

    //Bubble Sort
    public static void bubblesort(int[] arr){
        int n = arr.length;
        for(int i = 0 ; i < n-1 ; i++){
            for(int j = 0 ; j < n-i-1 ; j++){
                if(arr[j] > arr[j+1]){  //两数字交换
                    int t = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = t;
                }
            }
        }
    }

    //Selection Sort
    public static void selectionsort(int[] arr){
        int n = arr.length;
        for(int i = 0 ; i < n-1 ; i++){
            int min = i;
            for(int j = i+1 ; j < n ; j++){
                if(arr[min] > arr[j]){  //找最小值
                    min = j;
                }
            }
            int t = arr[i]; //两数交换
            arr[i] = arr[min];
            arr[min] = t;
        }
    }

    //Insertion Sort
    public static void insertionsort(int[] arr){
        int n = arr.length;
        for(int i = 1 ; i < n ; i++){
            int temp = arr[i];
            int j = i-1;
            while(j >= 0 && arr[j] > temp){ //持续比对是否比 temp 大
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
    }

    //Merge Sort
    public static void merge(int[] arr, int head, int mid, int tail){
        int lenA = mid - head + 1;
        int lenB = tail - (mid+1) + 1;
        int[] A = new int[lenA];    //左子数列
        int[] B = new int[lenB];    //右子数列
        int i,j;
        for(i = 0 ; i < lenA ; i++){
            A[i] = arr[head+i];
        }
        for(j = 0 ; j < lenB ; j++){
            B[j] = arr[mid+1+j];
        }
        i = 0;
        j = 0;
        int k = head;
        while(i < lenA && j < lenB){
            if(A[i] < B[j]){
                arr[k] = A[i];
                i++;
                k++;
            }
            else{
                arr[k] = B[j];
                j++;
                k++;
            }
        }
        //右子数列已经结束，将左子数列剩余的数复制到 arr
        while(i < lenA){
            arr[k] = A[i];
            i++;
            k++;
        }
        //左子数列已经结束，将右子数列剩余的数复制到 arr
        while(j < lenB){
            arr[k] = B[j];
            j++;
            k++;
        }
    }

    public static void mergesort(int[] arr, int head, int tail){
        if(head < tail){
            int mid = (head + tail) / 2;
            mergesort(arr, head, mid);
            mergesort(arr, mid+1, tail);
            merge(arr, head, mid, tail);    //合并
        }
    }
}

大家可以多执行几次，看看平均执行时间，我的实验结果是：merge > selection > insertion > bubble （速度），选择排序和插入排序其实时间非常相近，合并排序的话不用说，远远把其他三者甩在後头，是不是觉得很有趣呢？昨天提到的其他排序法大家也可以自己试试看哦！我们的「排序大集合」正式在五天的介绍下结束了。