iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
Software Development

30 天 Java 從陌生到更陌生系列 第 19

[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 (速度),選擇排序和插入排序其實時間非常相近,合併排序的話不用說,遠遠把其他三者甩在後頭,是不是覺得很有趣呢?昨天提到的其他排序法大家也可以自己試試看哦!我們的「排序大集合」正式在五天的介紹下結束了。


上一篇
[Day18] CH10:排序大家族——合併排序法
下一篇
[Day20] 來決鬥吧——ZeroJudge & LeetCode 解題
系列文
30 天 Java 從陌生到更陌生30

尚未有邦友留言

立即登入留言