Skip to content

[資料結構] 選擇排序法（Selection Sort）

選擇排序法（selection sort）同樣是最知名的排序演算法之一，也是相當穩定的排序法。不論是最好的狀況（best case）、平均狀況（average case）、還是最糟的狀況（worst case）通通都是 O(n^2) 的時間複雜度。

選擇排序法的原理

以遞增排序來說，通常是從列表中最初的索引開始，在一輪迭代中找出最小的數字，並把最小的數字與開頭的值進行交換；在第二輪的排序時，則忽略開頭的數字（因為已經是最小值了），從下一位數字開始再次尋找該輪迭代的最小值…… 依此類推，直到只剩下最後一個數字為止。

而最後一個數字一定是該列表的最大值，故不用再額外進行遍歷。

跟上次的氣泡排序法（bubble sort）還是一樣，這裡用以下列表作為範例：

[4, 5, 3, 1, 2, 7, 6]
  • 首先，我們紀錄開頭數字 4 為當前最小值，接著開始依序比較列表中的其他數字
  • 最後，我們發現 1 就是該列表中最小值，於是我們把 1 跟 4 的位置交換
[1, 5, 3, 4, 2, 7, 6]
  • 接著第二輪的迭代，我們紀錄開頭數字 5 為當前最小值（這次從第二個值開始）…… 依此類推。

最後，我們就會得到以下排序過的列表：

[1, 2, 3, 4, 5, 6, 7]

同樣也是非常單純直覺的排序方法。那麼，以下就是 sample code。

選擇排序法範例程式碼

複雜度

是複雜度比較穩定的方法，所需要的額外空間只有 O(1)，但是在較長的陣列中可能比較不適合使用時間複雜度這麼高的排序法。

Time ComplexityO(n^2)
Space ComplexityO(1)


C++ 範例程式碼

#include <iostream>
using namespace std;


void swap(int* n1, int* n2) {
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}


void printArr(int arr[], int size) {
    for (int i=0; i<size; ++i) {
        cout << arr[i] << " ";
    }

    cout << endl;
}


void selectionSort(int arr[], int size) {
    // Sort
    for (int i=0; i<size-1; ++i) {
        // Init
        int minIndex = i;

        for (int j=i+1; j<size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap
        swap(&arr[i], &arr[minIndex]);

        // Print progress
        cout << i+1 << ": ";
        printArr(arr, size);
    }
}


int main() {
    int arr[] = {4, 5, 3, 1, 2, 7, 6};
    int size = sizeof(arr) / sizeof(arr[0]); 
    selectionSort(arr, size);

    return 0;
}



Output:

1: 1 5 3 4 2 7 6 
2: 1 2 3 4 5 7 6 
3: 1 2 3 4 5 7 6 
4: 1 2 3 4 5 7 6 
5: 1 2 3 4 5 7 6 
6: 1 2 3 4 5 6 7


Python 範例程式碼

# coding: utf-8


def bubbleSort(arr, size):
    for i in range(size-1):
        # Init
        minIndex = i

        for j in range(i+1, size):
            if (arr[j] < arr[minIndex]):
                minIndex = j
        
        # Swap
        arr[i], arr[minIndex] = arr[minIndex], arr[i]

        # Print progress
        print("{}: {}".format(i+1, arr))


def main():
    # Init
    arr = [4, 5, 3, 1, 2, 7, 6]
    size = len(arr)

    # Sort
    bubbleSort(arr, size)


if __name__ == "__main__":
    main()



Output:

1: [1, 5, 3, 4, 2, 7, 6]
2: [1, 2, 3, 4, 5, 7, 6]
3: [1, 2, 3, 4, 5, 7, 6]
4: [1, 2, 3, 4, 5, 7, 6]
5: [1, 2, 3, 4, 5, 7, 6]
6: [1, 2, 3, 4, 5, 6, 7]

References

Read More

Tags:

Leave a Reply