山東理工大學ACM 1231：絕對值排序 - C語言解題詳解

題目描述

輸入 n（n ≤ 100）個整數，按照絕對值從大到小排序後輸出。題目保證每個測試實例中，所有數的絕對值互不相等。

輸入格式

輸入包含多組數據，每組佔一行。每行第一個數字為 n，隨後是 n 個整數。當 n = 0 時表示輸入結束，不處理該行。

輸出格式

對每個測試實例，輸出排序後的結果，相鄰兩數之間用一個空格隔開，每個實例佔一行。

範例

輸入範例

3 3 -4 2
4 0 1 2 -3
0

輸出範例

-4 3 2
-3 2 1 0

解題思路

由於 n ≤ 100，數據規模極小，可直接使用簡單的排序算法（如冒泡排序、選擇排序）或標準庫 qsort。關鍵在於比較函數：按絕對值降序排列。

參考代碼 (C語言)

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

int cmp(const void *a, const void *b) {
    int x = *(int *)a;
    int y = *(int *)b;
    return abs(y) - abs(x); // 絕對值降序
}

int main() {
    int n, a[100];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        qsort(a, n, sizeof(int), cmp);
        for (int i = 0; i < n; i++) {
            if (i) printf(" ");
            printf("%d", a[i]);
        }
        printf("\n");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n log n) 每組測試數據，n ≤ 100 時極快。
• 空間複雜度：O(n) 存儲數組。

注意事項

• 絕對值比較時注意 abs 函數需包含 stdlib.h 或 math.h。
• 輸入以 n = 0 結束，循環條件寫作 while(scanf("%d", &n) && n)。
• 輸出格式：數字間單空格，行末無多餘空格。