為何學排序？

排序為最基本也最容易上手也最泛用的演算法，解題方面有時候如果將資料排序過也會更容易解題或是大大降低時間複雜度，因此，如何更快的排序資料就成為了我們最基礎需要學的演算法

基本排序法

以下排序法在大部分題目通常都執行效率不佳，因此只作為必要知識介紹

選擇排序法 (Selection Sort)

• 找到需排序資料中未排序的部分中最小／最大值(極值)
• 將該資料與未排序的資料中最左邊／最右邊的資料相互換
• 將該資料設為已排序

Code:

void selection_sort(int arr[],int n){
    for(int i = 0;i < n - 1;i++){
        int num = arr[i],mx = i;
        for(int j = i + 1;j < n;j++){
            if(arr[j] < num){
                num = arr[j];
                mx = j;
            }
        }
        swap(arr[i],arr[mx]);
    }
}

時間複雜度：

氣泡／泡沫排序法 (Bubble Sort)

• 將欲排序資料中的未排序資料左右比較
• 如果右邊資料較小就互換
• 走到未排序資料中的最右邊後將該資料設為已排序

Code:

void bubble_sort(int arr[],int n){
    for(int i = n - 1;i > 0;i--){
        for(int j = 0;j < i;j++){
            if(arr[j + 1] < arr[j]){
                swap(arr[j],arr[j + 1]);
            }
        }
    }
}

時間複雜度：

插入排序法 (Insertion Sort)

從第二個資料開始，如果它比前一資料小，就往前放；直到比前一資料大，或變成第一資料為止。再對第三資料做相同的操作，直至排好所有的資料

• 將第 1 個資料先預設為已排序
• 從第 2 個資料開始，如果比前一資料小就往前移（互換），直到比前一資料大或是變成第一個資料
• 重複做 n 次將一資料插入"已經排序好的資料"之中

Code:

void insertion_sort(int arr[],int n){
    for(int i = 1;i < n;i++){
        for(int j = i;j > 0 && arr[j] < arr[j - 1];j--){
            swap(arr[j],arr[j - 1]);
        }
    }
}

時間複雜度：

題目練習

UVa 10327

總結

本文介紹基本的三種基本排序演算法：選擇排序、氣泡排序和插入排序。這些算法雖然簡單，但對初學者來說是學習排序的起點。然而，它們的效率較低（），在實際應用中不夠高效，因此更快速的排序演算法在處理大量數據時更為常見。排序是資訊科學中的基本主題，對於解決各種問題和提高程序效率都至關重要。

預告

明天會有更加快速且實用的排序演算法，大家可以好好期待