這裡所稱的排序(Sorting),是指將一串不規則的數值資料(如陣列資料)依照遞增或是遞減的方式重新編排。要將一串不規則的數值資料遞增或是遞減排列,方法當然不會只有一種,而不同方法排列資料的難易度、速度和其它特性自然也會有所不同。排序演算法(Sorting Algorithm)就是排列資料的方法,目前已知的方法有很多,在這篇文章中將會介紹比較實用的六種排序演算法,分別是氣泡排序(bubble sort)、交換排序(exchange sort)、選擇排序(selection sort)、插入排序(insertion sort)、快速排序(quick sort)和合併排序(merge sort)。



氣泡排序法(Bubble Sort)

氣泡排序法的概念

氣泡排序法(又稱泡沫排序法)是最常見的排序演算法,因為它簡單、易懂、容易撰寫,在優化過後的效能也不算太差。所謂「氣泡」,顧名思義,就是它的排序方式如同氣泡一般,不斷將最大的元素擠出(移動)到陣列最尾端,當所有元素都如同氣泡般被被擠出後,排序就完成了!

氣泡排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最尾端的位置,因為我們要先將整個陣列的最大值移動到陣列的最尾端。那麼,該如何從陣列中找到最大值並將其移動到最尾端呢?

從陣列最前方開始,逐次兩兩比較元素的大小,將兩個元素中較大的元素排在後面,即可逐漸將最大的元素從陣列前方擠到陣列後方。這就像是沉在水中的大氣泡,像要漂浮到水面上前,必須擠開其他的小氣泡一樣。

所以,若要擠出陣列的最大值至陣列的最尾端,位於陣列最前端的的69,要跟之後的元素(81)比大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

69比81小,所以不用換位置。然後再比81和30的大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

81比30大,所以81會擠開30,與30交換,排在30之後。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
           └─┘

然後再比81和38的大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

81比38大,所以81會擠開38,與38交換,排在38之後。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
               └─┘

繼續判斷大小並移動,直到最大值被擠到陣列最尾端:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9  81   2  47  61  32  79
                   └─┴┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  81  47  61  32  79
                       └─┴┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  81  61  32  79
                           └─┴┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  81  32  79
                               └─┴┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  81  79
                                   └─┴┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

陣列的最大元素「81」成功被擠出至最尾端,接著用同樣的方法繼續找出第二大的元素,並將其擠出至尾端第二個位置,再找出第三大的元素,並將其擠出至尾端第三個位置。直到所有元素都被擠出為止,陣列就排序完成了!過程如下:

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81
       └┬┘
      69 > 30

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  38   9   2  47  61  32  79  81
       └─┴┬┘
          69 > 38

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69   9   2  47  61  32  79  81
           └─┴┬┘
              69 > 9

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9  69   2  47  61  32  79  81
               └─┴┬┘
                  69 > 2

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  69  47  61  32  79  81
                   └─┴┬┘
                      69 > 47

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  69  61  32  79  81
                       └─┴┬┘
                          69 > 61

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  69  32  79  81
                           └─┴┬┘
                              69 > 32

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
                               └─┴┬┘
                                  69 < 79

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
       └┬┘
      30 < 38

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
           └┬┘
          38 > 9

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9  38   2  47  61  32  69  79  81
           └─┴┬┘
              38 > 2
                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
               └─┴┬┘
                  38 < 47

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
                       └┬┘
                      47 < 61

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
                           └┬┘
                          61 > 32

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81
                           └─┴┬┘
                              61 < 69

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81
       └┬┘
      30 > 9

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30   2  38  47  32  61  69  79  81
       └─┴┬┘
          30 > 2

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
           └─┴┬┘
              30 < 38

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
                   └┬┘
                  38 < 47

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
                       └┬┘
                      47 < 32

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81
                       └─┴┬┘
                          47 < 61

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81
       └┬┘
       9 > 2

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
       └─┴┬┘
           9 < 30

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
               └┬┘
               30 < 38

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
                   └┬┘
                   38 > 32

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                   └─┴┬┘
                       38 < 47

--到此雖然陣列已經排序完成,但演算法尚未結束--

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
           └┬┘
           9 < 30

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
               └┬┘
               30 < 32

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                   └┬┘
                   32 < 38

                   ●  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

                   ●  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
           └┬┘
           9 < 30

                   ●  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
               └┬┘
               30 < 32

               ●  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

               ●  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
           └┬┘
           9 < 30

           ●  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

           ○  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

---------------演算法至此才結束---------------

氣泡排序法的程式實作

/**
 * 氣泡排序法(Bubble Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void bubbleSort(final int[] array) {
    for (int i = array.length - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            final int jj = j + 1;
            if (array[j] > array[jj]) {
                final int buffer = array[j];
                array[j] = array[jj];
                array[jj] = buffer;
            }
        }
    }
}

氣泡排序法的優化

從上面氣泡排序法的排序例子中,可以看到陣列在排序的過程中早就已經明顯排好了,但程式依然必須要執行完整的迴圈後才會停止。所以我們可以在每次從陣列最前端擠出最大元素至尾端的時候,記錄是否有元素被擠出,如果沒有,表示陣列已經排列完成了,就不用再嘗試擠出所有的元素了。利用記錄陣列是否有元素被擠出的方式優化之後的氣泡排序法可以改寫如下:

/**
 * 氣泡排序法(Bubble Sort),能記錄是否有元素被擠出。
 *
 * @param array 傳入要排序的陣列
 */
public static void bubbleSort(final int[] array) {
    for (int i = array.length - 1; i > 0; --i) {
        boolean sorted = true;
        for (int j = 0; j < i; ++j) {
            final int jj = j + 1;
            if (array[j] > array[jj]) {
                final int buffer = array[j];
                array[j] = array[jj];
                array[jj] = buffer;
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
    }
}

雖然在上面氣泡排序法的排序例子中不明顯,但氣泡排序法還存在著另外一個問題,那就是當陣列最前端的幾個元素若不小心早就在過程中排序好了,在擠出最大元素至尾端的時候又會再次重複比較大小,會浪費許多時間在做同一件事情上。因此,可以改良一下氣泡排序法,使其能夠將最大元素從最前端擠到尾端,也可以將最小元素從最尾端擠到前端,雙管齊下。改良後的氣泡排序法程式如下:

/**
 * 氣泡排序法(Bubble Sort),最佳化版本,記錄是否有元素被擠出,同時擠出最大元素和最小元素。
 *
 * @param array 傳入要排序的陣列
 */
public static void bubbleSortOptimized(final int[] array) {
    final int e = array.length - 1;
    int i = 0;
    while (true) {
        boolean sorted = true;
        final int ee = e - i;
        for (int j = i; j < ee; ++j) {
            final int jj = j + 1;
            if (array[j] > array[jj]) {
                final int buffer = array[j];
                array[j] = array[jj];
                array[jj] = buffer;
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
        sorted = true;
        for (int j = ee - 1; j > i; --j) {
            final int jj = j - 1;
            if (array[j] < array[jj]) {
                final int buffer = array[j];
                array[j] = array[jj];
                array[jj] = buffer;
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
        ++i;
    }
}

氣泡排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

交換排序法(Exchange Sort)

交換排序法的概念

交換排序是最簡單的排序方法。從陣列最前端開始尋找最小的元素放置於最前端中,接著再從陣列次前端的位置開始尋找最小的元素放置於次前端中,在尋找最小元素的過程中,遇到比目前更小的元素就進行交換,最後就可以換成最小的元素。

交換排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最前端的位置,因為我們要先將整個陣列的最小值移動到陣列的最前端。那麼,該如何從陣列中找到最小值並將其移動到最前端呢?

從陣列最前端開始,與陣列之後的元素比大小,若找到比最前端還小的元素,就進行交換,如下表:

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

69比81小,所以不用換位置。然後再比69和30的大小,如下表:

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └─┬─┘
        69 > 30

69比30大,所以會與30交換。

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  81  69  38   9   2  47  61  32  79
       └───┘

繼續判斷大小並交換,直到判斷至最尾端:

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  81  69  38   9   2  47  61  32  79
       └──┬──┘
          30 < 38

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  81  69  38   9   2  47  61  32  79
       └───┬───┘
            30 > 9

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  81  69  38  30   2  47  61  32  79
       └───────┘

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  81  69  38  30   2  47  61  32  79
       └────┬────┘
               9 > 2

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
       └─────────┘

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
       └─────┬─────┘
                 2 < 47

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
       └──────┬──────┘
                   2 < 61

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
       └───────┬───────┘
                     2 < 32

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
       └────────┬────────┘
                       2 < 79

判斷至最尾端後,最前端的元素即可確定是陣列中最小的元素,接著用同樣的方法繼續找出第二小的元素,並將其交換至前端第二個位置,再找出第三小的元素,並將其交換至前端第三個位置。直到所有元素位置都被確認過之後,陣列就排序完成了!過程如下:

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  69  38  30   9  47  61  32  79
           └┬┘
          81 > 69

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  69  81  38  30   9  47  61  32  79
           └─┘

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  69  81  38  30   9  47  61  32  79
           └─┬─┘
            69 > 38

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  38  81  69  30   9  47  61  32  79
           └───┘

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  38  81  69  30   9  47  61  32  79
           └──┬──┘
              38 > 30

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  30  81  69  38   9  47  61  32  79
           └─────┘

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2  30  81  69  38   9  47  61  32  79
           └───┬───┘
                30 > 9

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
           └───────┘

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
           └────┬────┘
                   9 < 47

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
           └─────┬─────┘
                     9 < 61

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
           └──────┬──────┘
                       9 < 32

       ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
           └───────┬───────┘
                         9 < 79

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  81  69  38  30  47  61  32  79
               └┬┘
              81 > 69

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  69  81  38  30  47  61  32  79
               └─┘

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  69  81  38  30  47  61  32  79
               └─┬─┘
                69 > 38

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  38  81  69  30  47  61  32  79
               └───┘

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  38  81  69  30  47  61  32  79
               └──┬──┘
                  38 > 30

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
               └─────┘

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
               └───┬───┘
                    30 < 47

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
               └────┬────┘
                      30 < 61

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
               └─────┬─────┘
                        30 < 32

       ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
               └──────┬──────┘
                          30 < 79

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  81  69  38  47  61  32  79
                   └┬┘
                  81 > 69

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  69  81  38  47  61  32  79
                   └─┘

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  69  81  38  47  61  32  79
                   └─┬─┘
                    69 > 38

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └───┘

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └──┬──┘
                      38 < 47

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └───┬───┘
                        38 < 61

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └────┬────┘
                          38 > 32

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                   └─────────┘

       ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                   └─────┬─────┘
                            32 < 79

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                       └┬┘
                      69 < 81

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  69  81  47  61  38  79
                       └─┘

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  69  81  47  61  38  79
                       └─┬─┘
                        69 > 47

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  47  81  69  61  38  79
                       └───┘

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  47  81  69  61  38  79
                       └──┬──┘
                          47 < 61

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  47  81  69  61  38  79
                       └───┬───┘
                            47 > 38

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  81  69  61  47  79
                       └───────┘

       ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  81  69  61  47  79
                       └────┬────┘
                              38 < 79

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  81  69  61  47  79
                           └┬┘
                          81 > 69

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  81  61  47  79
                           └─┘

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  81  61  47  79
                           └─┬─┘
                            69 > 61

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  61  81  69  47  79
                           └───┘

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  61  81  69  47  79
                           └──┬──┘
                              61 > 47

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  81  69  61  79
                           └─────┘

       ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  81  69  61  79
                           └───┬───┘
                                47 < 79

       ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  81  69  61  79
                               └┬┘
                              81 > 69

       ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  81  61  79
                               └─┘

       ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  81  61  79
                               └─┬─┘
                                69 > 61

       ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  81  69  79
                               └───┘

       ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  81  69  79
                               └──┬──┘
                                  61 < 79

       ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  81  69  79
                                   └┬┘
                                  81 > 69

       ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                   └─┘

       ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                   └─┬─┘
                                    69 > 79

       ○  ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                       └┬┘
                                      81 > 79

       ○  ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                                       └─┘

       ○  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

----------------演算法至此結束----------------

交換排序法的程式實作

/**
 * 交換排序法(Exchange Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void exchangeSort(final int[] array) {
    final int l = array.length;
    final int e = l - 1;
    for (int i = 0; i < e; ++i) {
        for (int j = i + 1; j < l; ++j) {
            if (array[i] > array[j]) {
                final int buffer = array[j];
                array[j] = array[i];
                array[i] = buffer;
            }
        }
    }
}

交換排序法的優化

從上面的例子中,可以發現交換排序法在找到最小元素之前的交換都是毫無意義的,導致交換元素的次數變得十分的多。因此,若能減少沒有必要的交換次數,就可以讓程式效能大增。朝這個方向去優化交換排序法的結果,就是選擇排序法了。

交換排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n2) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

選擇排序法(Selection Sort)

選擇排序法的概念

選擇排序法也是很簡單的排序方法,為交換排序法的優化版,在使用交換排序法時尋找最小元素的過程中不直接交換陣列的元素,而是記下目前搜尋到最小元素的索引值,最後再進行元素交換。

選擇排序法的過程

建議先了解交換排序法的過程,再來看選擇排序法。

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最前端的位置,因為我們要先將整個陣列的最小值移動到陣列的最前端。那麼,該如何從陣列中找到最小值並將其移動到最前端呢?

先假設目前陣列最前端的元素為最小值,再與其之後的元素比大小,若找到比目前假設最小元素還小的元素,就記下索引值,如下表:

       ●
       ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

69比81小,假設的最小元素之索引位置不用更動。然後再比69和30的大小,如下表:

       ●
       ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └─┬─┘
        69 > 30

69比30大,所以最小元素之索引位置變成2。

       ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
               →

繼續判斷大小並更改最小元素之索引位置,直到判斷至最尾端:

       ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
               └┬┘
              30 < 38

       ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
               └─┬─┘
                30 > 9

       ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                       →

       ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                       └┬┘
                       9 > 2

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                           →

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                           └┬┘
                           2 < 47

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                           └─┬─┘
                             2 < 61

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                           └──┬──┘
                               2 < 32

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
                           └───┬───┘
                                 2 < 79

判斷至最尾端後,即可找到最小元素的位置,再將最前端的元素和最小元素交換,如下表:

       ●
                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
       └─────────┘

接著用同樣的方法繼續找出第二小的元素,並將其交換至前端第二個位置,再找出第三小的元素,並將其交換至前端第三個位置。直到所有元素位置都被確認過之後,陣列就排序完成了!過程如下:

       ○  ●
           ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
           └┬┘
           81 > 30

       ○  ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
               →

       ○  ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
               └┬┘
               30 < 38

       ○  ●
               ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                   └┬┘
                   38 > 9

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       →

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       └┬┘
                       9 < 69

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       └─┬─┘
                         9 < 47

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       └──┬──┘
                           9 < 61

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       └───┬───┘
                             9 < 32

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2  81  30  38   9  69  47  61  32  79
                       └────┬────┘
                               9 < 79

       ○  ●
                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
           └─────┘

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └┬┘
              30 < 38

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └─┬─┘
                30 < 81

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └──┬──┘
                  30 < 69

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └───┬───┘
                    30 < 47

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └────┬────┘
                      30 < 61

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └─────┬─────┘
                        30 < 32

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               └──────┬──────┘
                          30 < 79

       ○  ○  ●
               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
               │

       ○  ○  ○  ●
                   ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └┬┘
                  38 < 81

       ○  ○  ○  ●
                   ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └─┬─┘
                    38 < 69

       ○  ○  ○  ●
                   ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └──┬──┘
                      38 < 47

       ○  ○  ○  ●
                   ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └───┬───┘
                        38 < 61

       ○  ○  ○  ●
                   ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                   └────┬────┘
                          38 > 32

       ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                                       →

       ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  81  69  47  61  32  79
                                       └┬┘
                                      32 < 79

       ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                   └─────────┘

       ○  ○  ○  ○  ●
                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                       └┬┘
                      81 > 69

       ○  ○  ○  ○  ●
                           ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                           →

       ○  ○  ○  ○  ●
                           ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                           └┬┘
                          69 > 47

       ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                               →

       ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                               └┬┘
                              47 < 61

       ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                               └─┬─┘
                                47 > 38

       ○  ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                                       →

       ○  ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  81  69  47  61  38  79
                                       └┬┘
                                      38 < 79

       ○  ○  ○  ○  ●
                                       ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                       └───────┘

       ○  ○  ○  ○  ○  ●
                           ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                           └┬┘
                          69 > 47

       ○  ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                               →

       ○  ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                               └┬┘
                              47 < 61

       ○  ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                               └─┬─┘
                                47 < 81

       ○  ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  69  47  61  81  79
                               └──┬──┘
                                  47 < 79

       ○  ○  ○  ○  ○  ●
                               ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  61  81  79
                           └─┘

       ○  ○  ○  ○  ○  ○  ●
                               ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  61  81  79
                               └┬┘
                              69 > 61

       ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  61  81  79
                                   →

       ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  61  81  79
                                   └┬┘
                                  61 < 81

       ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  69  61  81  79
                                   └─┬─┘
                                    61 < 79

       ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                               └─┘

       ○  ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                   └┬┘
                                  69 < 81

       ○  ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                   └─┬─┘
                                    69 < 79

       ○  ○  ○  ○  ○  ○  ○  ●
                                   ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                   │

       ○  ○  ○  ○  ○  ○  ○  ○  ●
                                       ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                       └┬┘
                                      81 > 79

       ○  ○  ○  ○  ○  ○  ○  ○  ●
                                           ※
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                           →

       ○  ○  ○  ○  ○  ○  ○  ○  ●
                                           ※      
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                                       └─┘

       ○  ○  ○  ○  ○  ○  ○  ○  ○       
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

----------------演算法至此結束----------------

選擇排序法的程式實作

/**
 * 選擇排序法(Selection Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void selectionSort(final int[] array) {
    final int l = array.length;
    final int e = l - 1;
    for (int i = 0; i < e; ++i) {
        int k = i;
        for (int j = i + 1; j < l; ++j) {
            if (array[k] > array[j]) {
                k = j;
            }
        }
        if (k != i) {
            final int buffer = array[k];
            array[k] = array[i];
            array[i] = buffer;
        }
    }
}

選擇排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n2) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

插入排序法(Insertion Sort)

插入排序法的概念

在原陣列中建立一個保證順序的子陣列(通常位於陣列最前端),將子陣列之後的下一個元素視為要插入至子陣列的元素。將元素插入至保證順序的子陣列時,會從子陣列最尾端開始往前判斷要插入的元素是否大於等於目前判斷位置的元素,若有,則將元素放置於目前判斷位置後一個的位置;若沒有,則將目前判斷位置的元素往後移一個位置,拉出空格以便讓其他元素使用。

插入排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始,排序好的子陣列尚未建立,因此直接將索引0的元素作為進入子陣列的第一個元素。再來要將之後的元素插入至這個子陣列中,並確保子陣列元素的順序,插入元素的過程如下:

    ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

    ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

    ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

    ○  30  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  81  38   9   2  47  61  32  79
           └→┘

    ○  30  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  81  38   9   2  47  61  32  79
       └┬┘
      69 > 30

    30  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  69  81  38   9   2  47  61  32  79
       └→┘

    30  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  69  81  38   9   2  47  61  32  79
       │

    ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

    ○  ○  38  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  81  81   9   2  47  61  32  79
               └→┘

    ○  ○  38  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  81  81   9   2  47  61  32  79
           └┬┘
          69 > 38

    ○  38  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  69  81   9   2  47  61  32  79
           └→┘

    ○  38  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  69  81   9   2  47  61  32  79
       └┬┘
      30 < 38

    ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

    ○  ○  ○   9  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69  81   81   2  47  61  32  79
                   └→┘

    ○  ○  ○   9  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69  81   81   2  47  61  32  79
               └┬┘
              69 > 9

    ○  ○   9  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69  69   81   2  47  61  32  79
               └→┘

    ○  ○   9  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69  69   81   2  47  61  32  79
           └┬┘
          38 > 9

    ○   9  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  38  69  81   2  47  61  32  79
           └→┘

    ○   9  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  38  69  81   2  47  61  32  79
       └┬┘
      30 > 9

     9  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  30  38  69  81   2  47  61  32  79
       └→┘

     9  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值   30  30  38  69  81   2  47  61  32  79
       │

    ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  69  81   2  47  61  32  79
                       └┬┘
                      81 > 2

    ○  ○  ○  ○   2  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  69  81  81  47  61  32  79
                       └→┘

    ○  ○  ○  ○   2  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  69  81  81  47  61  32  79
                   └┬┘
                  69 > 2

    ○  ○  ○   2  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  69  69  81  47  61  32  79
                   └→┘

    ○  ○  ○   2  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  69  69  81  47  61  32  79
               └┬┘
              38 > 2

    ○  ○   2  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  38  69  81  47  61  32  79
               └→┘

    ○  ○   2  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  38  38  69  81  47  61  32  79
           └┬┘
          30 > 2

    ○   2  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  30  38  69  81  47  61  32  79
           └→┘

    ○   2  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30  30  38  69  81  47  61  32  79
       └┬┘
       9 > 2

     2  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9   9  30  38  69  81  47  61  32  79
       └→┘

     2  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    9   9  30  38  69  81  47  61  32  79
       │

    ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  69  81  47  61  32  79
                           └┬┘
                          81 > 47

    ○  ○  ○  ○  ○  47  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  69  81  81  61  32  79
                           └→┘

    ○  ○  ○  ○  ○  47  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  69  81  81  61  32  79
                       └┬┘
                      69 > 47

    ○  ○  ○  ○  47  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  69  69  81  61  32  79
                       └→┘

    ○  ○  ○  ○  47  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  69  69  81  61  32  79
                   └┬┘
                  38 < 47

    ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  69  81  61  32  79
                               └┬┘
                              81 > 61

    ○  ○  ○  ○  ○  ○  61  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  69  81  81  32  79
                               └→┘

    ○  ○  ○  ○  ○  ○  61  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  69  81  81  32  79
                           └┬┘
                          69 > 61

    ○  ○  ○  ○  ○  61  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  69  69  81  32  79
                           └→┘

    ○  ○  ○  ○  ○  61  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  69  69  81  32  79
                       └┬┘
                      47 < 61

    ○  ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  69  81  32  79
                                   └┬┘
                                  81 > 32

    ○  ○  ○  ○  ○  ○  ○  32  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  69  81  81  79
                                   └→┘

    ○  ○  ○  ○  ○  ○  ○  32  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  69  81  81  79
                               └┬┘
                              69 > 32

    ○  ○  ○  ○  ○  ○  32  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  69  69  81  79
                               └→┘

    ○  ○  ○  ○  ○  ○  32  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  69  69  81  79
                           └┬┘
                          61 > 32

    ○  ○  ○  ○  ○  32  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  61  69  81  79
                           └→┘

    ○  ○  ○  ○  ○  32  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  61  61  69  81  79
                       └┬┘
                      47 > 32

    ○  ○  ○  ○  32  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  47  61  69  81  79
                       └→┘

    ○  ○  ○  ○  32  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  47  47  61  69  81  79
                   └┬┘
                  38 > 32

    ○  ○  ○  32  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  38  47  61  69  81  79
                   └→┘

    ○  ○  ○  32  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  38  47  61  69  81  79
               └┬┘
              30 < 32

    ○  ○  ○  ○  ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  79
                                       └┬┘
                                      81 > 79

    ○  ○  ○  ○  ○  ○  ○  ○  79  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  81
                                       └→┘

    ○  ○  ○  ○  ○  ○  ○  ○  79  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  81  81
                                   └┬┘
                                  69 < 79

    ○  ○  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

----------------演算法至此結束----------------

插入排序法的程式實作

/**
 * 插入排序法(Insertion Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void insertionSort(final int[] array) {
    final int l = array.length;
    for (int i = 0; i < l; ++i) {
        final int temp = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > temp) {
            array[j + 1] = array[j--];
        }
        array[j + 1] = temp;
    }
}

插入排序法的複雜度

最差時間複雜度:O(n2) (排序逆序的陣列)

最佳時間複雜度:O(n) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

快速排序法(Quick Sort)

快速排序法的概念

快速排序法算是比較進階的排序方法,它的速度在大多數的情況下比前面四種都快,當然也難了許多。大致上來說,就是先在陣列中找出一個pivot(支點、中心點),想辦法將比pivot小的元素移動到pivot的左邊,比pivot大的元素移動到pivot的右邊,接著再用同樣的方法繼續對pivot的左邊子陣列和右邊子陣列進行排序。

快速排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

一開始,將陣列最左端(最前端)的位置與元素定為pivot,如下表所示:

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從最右端開始,尋找比pivot元素還要小的元素,可以找到索引8的32,如下表所示:

       ●                              <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從除了pivot的最左端開始,尋找比pivot元素還要更大的元素,可以找到索引1的81,如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

若比pivot更大的元素位置小於比pivot更小的元素位置(即比pivot更大的元素在比pivot更小的元素左邊),則交換兩個元素的位置,如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79
           └─────────────┘

接著從原先比pivot更小的元素位置繼續向左尋找比pivot更小的元素,可以找到索引7的61,如下表所示:

       ●  >                      <
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

因為索引7還在原先比pivot更大的元素位置之右邊,因此再繼續從原先比pivot更大的元素位置向右尋找比pivot更大的元素。可以找到索引8的81,如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

此時比pivot更大的元素位置大於比pivot更小的元素位置(即比pivot更大的元素在比pivot更小的元素右邊),則將比pivot更小的元素與pivot元素交換,如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79
       └─────────────┘

pivot元素交換了之後,可以發現pivot元素換到的位置,其左邊的元素正好都小於pivot元素,而右邊的元素正好都大於pivot元素。

                                   ○
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79

接下來再針對pivot元素左邊的子陣列和pivot右邊的子陣列進行排序,排序過程如下:

       ●                         | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

       ●                      < | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
數值   61  32  30  38   9   2  47     | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
數值   47  32  30  38   9   2  61     | 69  81  79
       └───────────┘

                               ○ | ○
索引    0   1   2   3   4   5   6 |  7   8   9
數值   47  32  30  38   9   2  61 | 69  81  79

       ●                     | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  < | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
數值   47  32  30  38   9   2     | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
數值    2  32  30  38   9  47     | 61 | 69  81  79
       └─────────┘

                           ○ | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
數值    2  32  30  38   9  47 | 61 | 69  81  79

       ●                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       <                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
數值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●             | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●          < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30   9  38 | 47 | 61 | 69  81  79
                    └─┘

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 | 32  30   9  38 | 47 | 61 | 69  81  79

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30  32  38 | 47 | 61 | 69  81  79
            └───┘

       ○ |         ○     | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30  32  38 | 47 | 61 | 69  81  79

       ○ | ●     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | <     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
數值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81
                                               └─┘

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ |     ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9
數值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79 | 81

----------------演算法至此結束----------------

快速排序法的程式實作

/**
 * 快速排序法(Quick Sort),遞迴版本。
 *
 * @param array 傳入要排序的陣列
 * @param start 傳入要排序的開始位置
 * @param end 傳入要排序的結束位置
 */
public static void quickSortRecursive(final int[] array, final int start, final int end) {
    final int x = array[start]; // pivot
    int l = start + 1;
    int r = end - 1;
    while (true) {
        while (r > start && array[r] >= x) {
            --r;
        }
        while (l <= r && array[l] <= x) {
            ++l;
        }
        if (l < r) {
            final int buffer = array[l];
            array[l] = array[r];
            array[r] = buffer;
        } else {
            if (r > start) {
                final int buffer = array[r];
                array[r] = array[start];
                array[start] = buffer;
            }
            break;
        }
    }
    final int ls = start, le = r;
    final int rs = r + 1, re = end;
    final int ll = le - ls, rl = re - rs;
    if (ll > 1) {
        quickSortRecursive(array, ls, le);
    }
    if (rl > 1) {
        quickSortRecursive(array, rs, re);
    }
}

/**
 * 快速排序法(Quick Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void quickSort(final int[] array) {
    quickSortRecursive(array, 0, array.length);
}

快速排序法的優化

在實作程式的時候,應該要避免使用遞迴(Recursive)的結構,遞迴的資源負擔很大,若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。雖然快速排序法是使用分治法(Divide and Conquer)的演算法,將大問題分解成小問題,解決完小問題後,大問題也就跟著解決了,用遞迴結構來實作十分容易,但建議還是使用稍微困難的迭代(Iterative)方式來完成。

由於快速排序法本身就是一種原地(in-place)演算法的關係,因此也很容易轉換成迭代的結構來實作,只需要多加一個stack陣列來模擬stack即可。至於這個stack陣列的大小只要大概相等於陣列的大小即可,再怎麼差的情況下stack的大小都不會增長到超過陣列的大小。

迭代版的快速排序法如下:

/**
 * 快速排序法(Quick Sort),迭代版本。
 *
 * @param array 傳入要排序的陣列
 */
public static void quickSortIterative(final int[] array) {
    final int[] stack = new int[array.length];
    int top = -1;
    int s, e;
    stack[++top] = 0;
    stack[++top] = array.length - 1;
    while (top >= 0) {
        e = stack[top--];
        s = stack[top--];
        final int x = array[s]; // pivot
        int l = s + 1;
        int r = e;
        while (true) {
            while (r > s && array[r] >= x) {
                --r;
            }
            while (l <= r && array[l] <= x) {
                ++l;
            }
            if (l < r) {
                final int buffer = array[l];
                array[l] = array[r];
                array[r] = buffer;
            } else {
                if (r > s) {
                    final int buffer = array[r];
                    array[r] = array[s];
                    array[s] = buffer;
                }
                break;
            }
        }
        final int ls = s, le = r - 1;
        final int rs = r + 1, re = e;
        final int ll = le - ls + 1, rl = re - rs + 1;
        if (ll > 1) {
            stack[++top] = ls;
            stack[++top] = le;
        }
        if (rl > 1) {
            stack[++top] = rs;
            stack[++top] = re;
        }
    }
}

為了避免遭遇固定的最差案例,pivot的選擇不應該每次都用最左邊的位置,隨機選擇會比較保險。另外,快速排序法在元素數量很少的情況下(不超過7個的時候),其實速度並不一定比簡單的排序演算法還要快,因為額外的資源負擔會比較大,所以在元素不超過7個的時候改用選擇排序法,會略為提升整體排序的速度。優化過後的快速排序法程式碼如下:

/**
 * 快速排序法(Quick Sort),迭代最佳化版本。
 *
 * @param array 傳入要排序的陣列
 */
public static void quickSortOptimized(final int[] array) {
    final int[] stack = new int[array.length];
    int top = -1;
    int s, e;
    stack[++top] = 0;
    stack[++top] = array.length - 1;
    while (top >= 0) {
        e = stack[top--];
        s = stack[top--];
        // 採用random pivot,先將random出來的pivot與最左邊交換
        final int p = (int) (Math.random() * (e - s + 1) + s);
        final int temp = array[p];
        array[p] = array[s];
        array[s] = temp;
        final int x = array[s]; // pivot
        int l = s + 1;
        int r = e;
        while (true) {
            while (r > s && array[r] >= x) {
                --r;
            }
            while (l <= r && array[l] <= x) {
                ++l;
            }
            if (l < r) {
                final int buffer = array[l];
                array[l] = array[r];
                array[r] = buffer;
            } else {
                if (r > s) {
                    final int buffer = array[r];
                    array[r] = array[s];
                    array[s] = buffer;
                }
                break;
            }
        }
        final int ls = s, le = r - 1;
        final int rs = r + 1, re = e;
        final int ll = le - ls + 1, rl = re - rs + 1;
        if (ll > 7) {
            stack[++top] = ls;
            stack[++top] = le;
        } else if (ll > 1) {
            for (int i = ls; i < le; ++i) {
                int k = i;
                for (int j = i + 1; j <= le; ++j) {
                    if (array[k] > array[j]) {
                        k = j;
                    }
                }
                if (k != i) {
                    final int buffer = array[k];
                    array[k] = array[i];
                    array[i] = buffer;
                }
            }
        }
        if (rl > 7) {
            stack[++top] = rs;
            stack[++top] = re;
        } else if (rl > 1) {
            for (int i = rs; i < re; ++i) {
                int k = i;
                for (int j = i + 1; j <= re; ++j) {
                    if (array[k] > array[j]) {
                        k = j;
                    }
                }
                if (k != i) {
                    final int buffer = array[k];
                    array[k] = array[i];
                    array[i] = buffer;
                }
            }
        }
    }
}

快速排序法的複雜度

最差時間複雜度:O(n2) (選擇的pivot剛好都是最大或最小值)

最佳時間複雜度:O(nlogn) (選擇的pivot剛好都是中間值)

平均時間複雜度:O(nlogn)

額外最差空間複雜度:O(logn)(遞迴)、O(n)(迭代)

合併排序法(Merge Sort)

合併排序法的概念

合併排序法是最典型的分治(Divide and Conquer)演算法,將一整個陣列分割成一個個元素,再兩兩一組依照元素大小填入至新的空間中來合併成新的、已經排序好的陣列。

快速排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

首先將陣列對半切成:

索引    0   1   2   3   4 |   5   6   7   8   9
數值   69  81  30  38   9 |   2  47  61  32  79

再對半切成:

索引    0   1 |  2   3   4 ||   5   6 |   7   8   9
數值   69  81 | 30  38   9 ||   2  47 |  61  32  79

再對半切成:

索引    0 |   1 ||  2 |   3   4 |||   5 |   6 ||   7 |   8   9
數值   69 |  81 || 30 |  38   9 |||   2 |  47 ||  61 |  32  79

再對半切成:

索引    0 ||   1 |||  2 ||   3 |   4 ||||   5 ||   6 |||   7 ||   8 |   9
數值   69 ||  81 ||| 30 ||  38 |   9 ||||   2 ||  47 |||  61 ||  32 |  79

已經不能再切了,即可開始合併:

索引    0 |   1 ||  2 |   3   4 |||   5 |   6 ||   7 |   8   9
數值   69 |  81 || 30 |   9  38 |||   2 |  47 ||  61 |  32  79
                         └─┘                         └─┘

繼續合併:

索引    0   1 |  2   3   4 ||   5   6 |   7   8   9
數值   69  81 |  9  30  38 ||   2  47 |  32  61  79
       └─┘   └─┴─┘     └─┘    └─┴─┘

繼續合併:

索引    0   1   2   3   4 |  5   6   7   8   9
數值    9  30  38  69  81 |  2  32  47  61  79
       └─┴─┴─┴─┘   └─┴─┴─┴─┘

繼續合併:

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └─┴─┴─┴─┴─┴─┴─┴─┴─┘

以上過程看起來十分直覺,但是實作起來需要額外的空間來協助進行排序。

合併排序法的程式實作

/**
 * 合併排序法(Merge Sort),遞迴版本。
 *
 * @param array 傳入要排序的陣列
 * @param buffer 儲存排序時需要用到的額外陣列空間
 * @param start 傳入要排序的開始位置
 * @param end 傳入要排序的結束位置
 */
public static void mergeSortRecursive(final int[] array, final int[] buffer, final int start, final int end) {
    final int l = end - start;
    if (l < 2) {
        return;
    }
    final int mid = l / 2 + start;
    int ls = start;
    final int le = mid;
    int rs = le;
    final int re = end;
    mergeSortRecursive(array, buffer, ls, le);
    mergeSortRecursive(array, buffer, rs, re);
    int k = start;
    while (ls < le && rs < re) {
        buffer[k++] = array[ls] < array[rs] ? array[ls++] : array[rs++];
    }
    while (ls < le) {
        buffer[k++] = array[ls++];
    }
    while (rs < re) {
        buffer[k++] = array[rs++];
    }
    System.arraycopy(buffer, start, array, start, l);
}

/**
 * 合併排序法(Merge Sort)。
 *
 * @param array 傳入要排序的陣列
 */
public static void mergeSort(final int[] array) {
    mergeSortRecursive(array, new int[array.length], 0, array.length);
}

合併排序法的優化

在實作程式的時候,應該要避免使用遞迴(Recursive)的結構,遞迴的資源負擔很大,若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。雖然合併排序法使用遞迴結構來實作十分容易,但建議還是使用稍微困難的迭代(Iterative)方式來完成。

為了化簡遞迴轉迭代結構時的問題,在這裡不採取從中間開始分割的方式,而是直接跳過分割的動作,從合併開始進行。在觀察合併排序法的分割過程後,其實不難發現完整的子陣列的長度,合併過後的長度都會再乘上2,且即便是未達2的乘冪長度的陣列,也能進行合併的動作。也就是說,分割的動作其實並非必要,可以直接從前端開始直接合併2的乘冪個元素,先從1(20)個元素兩兩開始合併,再從2(21)個元素兩兩開始合併,再從4(22)個元素兩兩開始合併,再從8(23)個元素兩兩開始合併,依此類推。因此可以寫出如下的迭代版合併排序法:

/**
 * 合併排序法(Merge Sort),迭代版本。
 *
 * @param array 傳入要排序的陣列
 */
public static void mergeSortIterative(final int[] array) {
    final int length = array.length;
    final int[] temp = array.clone();

    for (int i = 1; i < length; i *= 2) {
        final int ii = i * 2;
        final int je = length - i;
        for (int j = 0; j < je; j += ii) {
            int e = j + ii;
            if (e > length) {
                e = length;
            }
            int ls = j;
            int rs = ls + i;
            int r = rs;
            int k = j;
            while (ls < rs && r < e) {
                if (temp[ls] - temp[r] >= 0) {
                    array[k++] = temp[r++];
                } else {
                    array[k++] = temp[ls++];
                }
            }

            while (ls < rs) {
                array[k++] = temp[ls++];
            }
            while (r < e) {
                array[k++] = temp[r++];
            }
            System.arraycopy(array, j, temp, j, e - j);
        }
    }
}

合併排序法的複雜度

最差時間複雜度:O(nlogn)

最佳時間複雜度:O(nlogn)

平均時間複雜度:O(nlogn)

額外最差空間複雜度:O(n)

排序演算法速度測試

測試使用以上提到的不同演算法來排序同樣的陣列,陣列長度為75000。其所花費的時間如下:

亂序陣列排序速度測試

選擇排序法:6112 ms
插入排序法:9675 ms
氣泡排序法:27076 ms
最佳化的氣泡排序法:16411 ms
交換排序法:26821 ms
合併排序法:29 ms
快速排序法:29 ms
最佳化的快速排序法:27 ms

正序陣列排序速度測試

選擇排序法:6918 ms
插入排序法:1 ms
氣泡排序法:0 ms
最佳化的氣泡排序法:0 ms
交換排序法:7475 ms
合併排序法:37 ms
快速排序法:5944 ms
最佳化的快速排序法:4 ms

反序陣列排序速度測試

選擇排序法:7490 ms
插入排序法:19428 ms
氣泡排序法:21620 ms
最佳化的氣泡排序法:16956 ms
交換排序法:22056 ms
合併排序法:15 ms
快速排序法:5286 ms
最佳化的快速排序法:5 ms

其它更進階的排序演算法

另外還有其它針對特定案例來使用的排序演算法,如果用對地方的話,效果會比上面的六種排序演算法還要好很多。

例如針對小範圍整數進行排序的「計數排序(Counting Sort)」:

https://magiclen.org/counting-sort/

MagicSort

MagicSort是一個Java函式庫,完整實作並應用了多個排序演算法,有興趣者可以參考這篇文章:

https://magiclen.org/magicsort/