藍橋杯 BASIC 排序題完整解析

本題核心需求是對整數序列進行排序，資料範圍較小（N ≤ 200），可採用標準庫排序或自行實作經典演算法。以下提供三種不同複雜度的解法供參考。

解法一：標準庫 sort（推薦）

時間複雜度 O(N log N)，程式碼最簡潔，實戰首選：

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 210

int main() {
    int n, num[MAX];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    
    sort(num, num + n); // 內建快速排序
    
    for (int i = 0; i < n; i++) cout << num[i] << " ";
    return 0;
}

解法二：冒泡排序（教學用）

時間複雜度 O(N²)，適合理解排序基本原理：

#include <iostream>
using namespace std;

#define MAX 210

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

int main() {
    int n, num[MAX];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    
    bubble_sort(num, n);
    
    for (int i = 0; i < n; i++) cout << num[i] << " ";
    return 0;
}

解法三：qsort（C 風格）

需自行實作比較函數，展示 C 語言標準庫用法：

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int n, num[210];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &num[i]);
    
    qsort(num, n, sizeof(int), cmp);
    
    for (int i = 0; i < n; i++) printf("%d ", num[i]);
    return 0;
}

關鍵點總結

• 資料範圍小（N ≤ 200），O(N²) 演算法也能通過
• 實戰競賽首選 std::sort，效率高且不易出錯
• 注意陣列大小定義需 ≥ 200，建議留餘量設為 210
• 輸出格式：數字間以空格分隔，行尾可有多餘空格