學完這些基本的資料結構之後，我想來介紹一些演算法
因為之前看過一句話

Algorithms + Data Structures = Programs
by Niklaus Wirth

一個好的程式需要演算法+資料結構，還記得在 Day 1 有說過怎麼讓程式不只會跑，還能跑得又快又好嗎，所以這幾天應該都會來介紹演算法
事不遲疑，趕快來介紹吧~

排序演算法

排序(Sort) 就是將資料由小到大或由大到小排列。

排序的分類方式

排序的分類方式有很多種，我這邊先講比較常見的三種

依資料量多寡(記憶體使用量) :

• 內部排序 (internal sort) : 排序的資料量較少，排序可以在主記憶體中完成。
• 外部排序 (external sort) : 資料量較大，主記憶體不夠排序，需要搭配輔助記憶體(如硬碟)來完成

依比較方式來排序 :

• 比較型排序 (Comparison-based sorting ) : 透過鍵值（key）來比較操作，時間複雜度至少需要 O(n log n)
• 非比較型排序 (Non-comparison Sort) : 不靠兩兩比大小來排順序，而是直接利用資料本身的特徵（像是數字有幾位數、值的範圍有多大）來決定位置， 時間複雜度最快可以 O(n)

依穩定性 :

• 穩定排序 (Stable Sort)：例如有兩個鍵值 (key) 相同的元素，排序前後的相對順序保持不變
• 不穩定排序 (Unstable Sort)：鍵值相同的元素，排序後相對順序變了，那就是不穩定的排序

常見排序法與時間複雜度

n：排序資料筆數

接下來我會先介紹氣泡排序、選擇排序、和插入排序

一、氣泡排序(Bubble Sort)

比較相鄰的兩個元素，如果前面的資料比後面的大就交換

例如 : [9,2,14,0]

第一輪，[2 9] 交換，[9 14]交換，[14 0]交換
可以發現最大值14跑到最後面

回到頭繼續比較

程式碼

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

二、選擇排序(Selection Sort)

每輪都從還沒排序好的部分裡找出最小值，把它換到最前面。

第二輪 : 2 已經是最小值了

程式碼

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;                          
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 找到更小的,更新索引
            }
        }
        swap(arr[i], arr[minIndex]); // 一輪只交換一次
    }
}

明天我們會繼續看其他的排序方法 !

參考資料和書籍

1. https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb
2. https://www.geeksforgeeks.org/dsa/classification-of-sorting-algorithms/