【筆記】Sorting 排序

Bubble sort 泡沫排序法

【原理】把大泡泡往下沉,小泡泡向上浮。
【複雜度】O(N2)
【練習】a539: 10327 – Flip Sort題解

for (int i=N-2; i>=0; i--){
    for (int j=0; j<=i; j++){
        if (a[j] > a[j+1]) swap(a[j], a[j+1]);
    }
}

Insertion sort 插入排序法

【原理】逐一檢查每個數字,把數字插入合適的位置。
【複雜度】O(N2)

for (int i=1; i<N; i++) {
    int key = a[i];
    int j = i - 1;
    while (key < a[j] && j >= 0) {
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = key;
}

Selection sort 選擇排序法

【原理】從頭開始檢查每個位置,把它跟其後最小的數字進行對調。
【複雜度】O(N2)

for (int i=0; i<N-1; i++) {
    int mn = a[i];
    int pos = i;
    for (int j=i+1; j<N; j++){
        if (a[j] < mn){
            mn = a[j];
            pos = j;
        }
    }
    swap(a[i], a[pos]);
}
分享本文 Share with friends