构建高效nlogn算法实现矩阵按行/列排序（保留元素）

首先，你的需求完全可以通过C标准库中的qsort函数实现——它的时间复杂度是O(n log n)，刚好适配大规模矩阵的场景。核心思路是针对两种排序需求，分别编写对应的比较函数，然后把结构体数组和比较函数传给qsort即可，既高效又省心，完全不需要自己实现排序算法。

1. 行优先排序（先按行排序，再按列排序） #

这种排序逻辑是：先按元素的行号line从小到大排序；如果行号相同，再按列号column从小到大排序。对应的比较函数如下：

int compareRowFirst(const void *a, const void *b) {
    const Matrix *matA = (const Matrix *)a;
    const Matrix *matB = (const Matrix *)b;
    
    // 先比较行号
    if (matA->line != matB->line) {
        return matA->line - matB->line;
    }
    // 行号相同则比较列号
    return matA->column - matB->column;
}

调用方式很简单，直接把结构体数组、元素数量、单个元素大小和比较函数传给qsort：

// 对matrix数组的前numb_of_matrix个元素执行行优先排序
qsort(matrix, numb_of_matrix, sizeof(Matrix), compareRowFirst);

2. 列优先排序（先按列排序，再按行排序） #

这种排序逻辑刚好相反：先按元素的列号column从小到大排序；如果列号相同，再按行号line从小到大排序。对应的比较函数：

int compareColumnFirst(const void *a, const void *b) {
    const Matrix *matA = (const Matrix *)a;
    const Matrix *matB = (const Matrix *)b;
    
    // 先比较列号
    if (matA->column != matB->column) {
        return matA->column - matB->column;
    }
    // 列号相同则比较行号
    return matA->line - matB->line;
}

调用方式同样直接：

// 对matrix数组的前numb_of_matrix个元素执行列优先排序
qsort(matrix, numb_of_matrix, sizeof(Matrix), compareColumnFirst);

关键细节说明 #

• 为什么用qsort？因为它是C标准库实现的高效排序算法（通常是快速排序），时间复杂度稳定在O(n log n)，完全满足你对大规模矩阵的性能要求，不需要自己造轮子。
• 比较函数的返回值：严格遵循qsort的要求——返回负整数表示a排在b前面，正整数表示b排在a前面，0表示两者相等。这里用无符号整数的差值是安全的，因为行号和列号都是非负的。
• 元素完整性：排序过程中只会调整结构体数组中元素的位置，不会修改value、line、column的数值，完全保留所有矩阵元素的信息。

内容的提问来源于stack exchange，提问作者Big Bear