C語言實現數組元素排名輸出：處理重複值的排序索引算法

問題描述

輸入數組長度 n 及 n 個整數，輸出每個元素在「從小到大排序後」的名次（排名）。相同值享受同一名次（如 1,2,2,4），輸出順序與輸入順序一致。

樣例：

輸入:  4
      -3 75 12 -3
輸出:  1 3 2 1
說明: 排序後 -3, -3, 12, 75 → 名次 1,1,2,3
      原順序 -3(第1)→1, 75→3, 12→2, -3(第4)→1

算法思路

1. 定義結構體保存 value（值）和 pos（原始索引）。
2. 將數組轉為結構體數組，調用 qsort 按 value 升序排序。
3. 遍歷排序後數組，維護 rank（當前名次）與 last_val（上一值）：
   • 若 value != last_val，rank++，更新 last_val。
   • 將 rank 寫入結果數組 result[pos]。
4. 按原始順序輸出 result。

完整代碼

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

typedef struct { int value; int pos; } Elem;

int cmp(const void *a, const void *b) {
    int v1 = ((Elem*)a)->value;
    int v2 = ((Elem*)b)->value;
    return (v1 > v2) - (v1 < v2); // 避免溢出的三元比較
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;

    Elem *arr = malloc(n * sizeof(Elem));
    int *result = malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i].value);
        arr[i].pos = i;
    }

    qsort(arr, n, sizeof(Elem), cmp);

    int rank = 0, last = arr[0].value + 1; // 確保第一個元素觸發 rank++
    for (int i = 0; i < n; ++i) {
        if (arr[i].value != last) {
            last = arr[i].value;
            ++rank;
        }
        result[arr[i].pos] = rank;
    }

    for (int i = 0; i < n; ++i) {
        printf("%d%c", result[i], i == n-1 ? '\n' : ' ');
    }

    free(arr);
    free(result);
    return 0;
}

關鍵點

• 穩定性：qsort 不保證穩定，但我們通過 pos 記錄原位置，最終按 pos 寫入結果，天然解決穩定性問題。
• 重複值同名次：last 變量配合 rank 遞增邏輯完美處理並列排名。
• 內存管理：動態分配適應任意 n，用完釋放。