華為機試：倒錐形數組排序——從暴力排序到雙端填充的 O(n log n) 解法

題目理解

給定 n 個整數，重新排列成「倒錐形」：最大值置中，左右兩側遞減。具體規律：

• 排序後數組 a[0] ≤ a[1] ≤ ... ≤ a[n-1]
• 結果數組 mid = (n-1)/2 處放最大值 a[n-1]
• 依次向左、向右交替填入次大值：mid-1、mid+1、mid-2、mid+2...

例如 n=5, a=[1,2,3,4,5] → 結果 [2,4,5,3,1]（索引 2 為最大值 5）。

演算法步驟

1. 輸入驗證：n > 0、數值範圍檢查（題目通常限定 |val| ≤ 1000）。
2. 排序：qsort 或冒泡（n 較小時），升序。
3. 雙端填充：

   int mid = (n - 1) / 2;
   output[mid] = input[n - 1];  // 最大值置中
   int left = mid - 1, right = mid + 1;
   for (int i = n - 2, side = 0; i >= 0; --i, side ^= 1) {
       if (side == 0) output[left--] = input[i];
       else           output[right++] = input[i];
   }
   

4. 輸出：空格分隔，行末換行。

完整代碼（含動態分配與錯誤處理）

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

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

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

    int *input = malloc(n * sizeof(int));
    int *output = malloc(n * sizeof(int));
    if (!input || !output) { perror("malloc"); return 1; }

    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &input[i]) != 1) { free(input); free(output); return 1; }
    }

    qsort(input, n, sizeof(int), cmp);

    int mid = (n - 1) / 2;
    output[mid] = input[n - 1];
    int left = mid - 1, right = mid + 1;
    for (int i = n - 2, side = 0; i >= 0; --i, side ^= 1) {
        if (side == 0) output[left--] = input[i];
        else           output[right++] = input[i];
    }

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

    free(input);
    free(output);
    return 0;
}

複雜度分析

• 時間：O(n log n)（排序主導），填充 O(n)。
• 空間：O(n)（輸入+輸出數組）。

常見錯誤與調試技巧

1. 中間索引計算：(n-1)/2 對奇偶 n 均正確（偶數時偏左）。
2. 左右交替邏輯：用 side ^= 1 替代 if-else 翻轉，簡潔高效。
3. 邊界檢查：left、right 不會越界，因為總共恰好填入 n-1 個元素。
4. 內存洩漏：所有 malloc 必須配對 free，異常路徑亦同。

擴展：若要求「正錐形」（最小值置中）？

只需將排序改為降序，或填充時從 input[0] 開始遞增取值，邏輯完全對稱。