6. 排序 (上篇)

關於排序本篇將討論以下幾個項目

1. 什麼是穩定的排序？

2. 什麼是空間複雜度(Space Complexity)？

3. 氣泡排序(Bubble Sort)

4. 選擇排序(Selection Sort)

測試環境：

OS：Windows 10
IDE：Visual Studio 2019

1. 什麼是穩定的排序？

簡單來說，資料經過排序後，值相同的資料仍然保持與排序前相同順序

圖中排序前 3L 在 3R 的左邊，排序後 3L 依舊在 3R 的左邊則稱為穩定排序
圖中排序前 3L 在 3R 的左邊，排序後 3L 在 3R 的右邊則稱為不穩定排序

是不是穩定排序有什麼差別？

單次排序不一定會有問題，不過在多次排序的需求下就會有明顯差異，舉個例來說，今天有一些訂單資訊，先以日期來排序，再以金額做排序，此時若是穩定排序在經過金額排序後，能得到同金額下日期是依序排列的訂單資訊，但若是不穩定排序則前次排序就不具意義了。

2. 什麼是空間複雜度(Space Complexity)？

額外使用的記憶體空間越多，空間複雜度越高

排序的過程中，若使用到額外的記憶體空間作為暫存，就需要考慮空間複雜度，而額外使用的記憶體越少空間複雜度越低

// 不論執行多少次，都只需要一個元素的記憶體空間
空間複雜度：O(1)

// 執行 n 次就需要 n 個元素的記憶體空間
空間複雜度：O(n)

3. 氣泡排序(Bubble Sort)

1. 由小到大排序
2. 由最左邊的元素開始與右邊元素比較，若左邊元素較大，則互相對調位置，若相同則不對調
3. 每輪比較至少會將一個元素放置於正確位置
4. 比較後，已知位於正確位置元素不參與下一輪比較
5. 完成排序

時間複雜度 & 空間複雜度 & 是否穩定：

    // 第一次比較 n-1 個元素，順序恰好為由小到大時
    最佳情況時間複雜度：O(n)

    // 剛好為倒序時
    // (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = n(n - 1) / 2
    最壞情況時間複雜度：O(n²)

    平均情況時間複雜度：O(n²)

    // 只需一個元素的記憶體空間作為對調使用
    空間複雜度：O(1)

    // 相鄰元素在值相等時不會交換
    是穩定排序

接下來以 C# 實作 氣泡排序(Bubble Sort)

範例：

        public int[] BubbleSort(int[] intArray)
        {
            // 每次比較會得到一個順序正確值，最後一個值不用比較
            // 故共需比較 intArray.Length - 1 輪
            for (var i = intArray.Length - 1; i > 0; i--)
            {
                // 比較是否交換次數
                for (var j = 0; j < i; j++)
                {
                    if (intArray[j] <= intArray[j + 1]) continue;

                    var temp = intArray[j];
                    intArray[j] = intArray[j + 1];
                    intArray[j + 1] = temp;
                }
            }

            return intArray;
        }

操作 & 結果

4. 選擇排序(Selection Sort)

1. 由小到大排序
2. 第一輪，找出所有元素中最小的元素，與第一個位置元素交換
3. 第 N 輪，於未排序元素中找出最小的元素，與第 N 個位置元素交換
4. 完成排序

時間複雜度 & 空間複雜度 & 是否穩定：

    // 所有情況下皆須找到最大(小)值
    // (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = n(n - 1) / 2
    最佳情況時間複雜度：O(n²)
    最壞情況時間複雜度：O(n²)
    平均情況時間複雜度：O(n²)

    // 只需兩個元素的記憶體空間作為對調 & 紀錄最小值 index 使用
    空間複雜度：O(1)

    // 找出最大(小)值後直接交換位置，元素順序可能被改變
    不是穩定排序

接下來以 C# 實作 選擇排序(Selection Sort)

範例：

        public int[] SelectionSort(int[] intArray)
        {
            for (int i = 0; i < intArray.Length; i++)
            {
                // 未排序值中最小值的 index
                var smallestIndex = i;

                // 遍歷所有未排序尋找最小值 index
                for (int j = i + 1; j < intArray.Length; j++)
                {
                    if (intArray[smallestIndex] > intArray[j])
                    {
                        smallestIndex = j;
                    }
                }

                var temp = intArray[i];
                intArray[i] = intArray[smallestIndex];
                intArray[smallestIndex] = temp;
            }

            return intArray;
        }

操作 & 結果

總結

本篇介紹了氣泡排序(Bubble Sort) & 選擇排序(Selection Sort)，建議在看完文字與圖片說明後先別看文章中的程式範例，試著自行將理解過後的文字轉換成程式碼印象會更加深刻。

文章中的程式範例是依據文字說明來呈現，可以思考看看如何在取得正確排序的前提下，更進一步優化程式的效能。

新手上路，若有錯誤還請告知，謝謝