二維數組按指定列排序 穩定排序鏈式比較

問題

m×n 整數矩陣，按第 i 列（1-based）為主鍵排序。若相等則按 i+1 列、i+2 列...遞歸比較，直到最後一列。完全相等保持原序（穩定排序）。

關鍵洞察：從最後一列向前穩定排序

若從主鍵列開始排序，後續列的相對順序會被打亂。正確做法：從最後一列逆序向主鍵列，每步用穩定排序（如冒泡、歸併、std::stable_sort）。

冒泡排序變形實現（原地、穩定）

void rangeArray(int* arr, int m, int n, int col) { // col 1-based
    if (!arr || m <= 0 || n <= 0 || col < 1 || col > n) return;
    int* tmp = new int[n];
    for (int c = n-1; c >= col-1; --c) { // 從最後一列到指定列
        for (int i = 0; i < m-1; ++i) {
            for (int j = 0; j < m-1-i; ++j) {
                if (arr[j*n + c] > arr[(j+1)*n + c]) {
                    // 整行交換
                    memcpy(tmp, arr + j*n, n*sizeof(int));
                    memcpy(arr + j*n, arr + (j+1)*n, n*sizeof(int));
                    memcpy(arr + (j+1)*n, tmp, n*sizeof(int));
                }
            }
        }
    }
    delete[] tmp;
}

C++ STL 版本（更簡潔）

void rangeArraySTL(vector<vector<int>>& mat, int col) { // col 0-based
    stable_sort(mat.begin(), mat.end(),
        [col](const vector<int>& a, const vector<int>& b) {
            for (int c = col; c < (int)a.size(); ++c)
                if (a[c] != b[c]) return a[c] < b[c];
            return false; // 完全相等保持原序
        });
}

複雜度

• 冒泡：O((n-col+1) · m²) —— m,n 小時可接受
• STL stable_sort：O((n-col+1) · m log m) —— 推薦
• 空間：O(n) 臨時行緩衝 / O(log m) 遞歸棧

示例驗證

輸入 (按第2列排):
1 2 3
2 3 4
2 3 1
1 3 1

輸出:
1 2 3   (第2列=2)
2 3 1   (第2列=3, 第3列=1)
1 3 1   (第2列=3, 第3列=1, 原序)
2 3 4   (第2列=3, 第3列=4)