C++基于平均行值的二维数组行排序

Question

Helo，

我想知道是否有任何工作方法？ 我正在尝试做这项工作，但没有运气。

int mat[3][3]; 

    mat[0][0] = 4;mat[0][1] = 5;mat[0][2] = 3; 

    mat[1][0] = 3;mat[1][1] = 2;mat[1][2] = 1; 

    mat[2][0] = 1;mat[2][1] = 8;mat[2][2] = 9; 

任何想法？ :)

Answer 1

您应该创建一个临时数据结构，它是一个元组数组。元组将是行索引和该行索引的平均值。然后使用标准的sort（）函数根据平均值对这个元组数组进行排序。然后，运行已排序的元组数组重新计算已排序的矩阵。

这会给您在排序例程完成的交换过程中不复制矩阵行的性能好处。如果您的行中只有3个元素，则可以交换整行。但是，随着您增加列数，交换将成为瓶颈。

在“伪码”你可以做这样的事情：

function sort(input, numrows, numcols) 
{ 
    pair<int, int> index[numrows]; 

    for (int i=0 to numrows) { 
     index[i].second = i; 
     // compute average of row[i] in the input matrix 
     index[i].first = average_of_row(&input[i]); 
    } 

    // STL sort will sort the pair based on the average (.first member) 
    sort(index.begin(), index.end()); 

    for (int i=0 to index.size()) 
    { 
     // copy rows from input matrix to output matrix 
     copy_row(&input[index[i].second], &output_matrix[i]); 
    } 

    return output; 
} 

Answer 2

一个更习惯性的C++方式这样做（与您的原始数组阵列）将是一个矢量向量，即。 std::vector<std::vector<int> >，然后在顶层向量上调用std::sort。您可以通过sort自定义谓词，根据它们的平均值比较两行。

Answer 3

继@彼得的建议，

#include <algorithm> 
#include <numeric> 
#include <vector> 
using namespace std; 

bool comp(vector<int> a, vector<int> b) { 
    if (a.size() == 0 || b.size() == 0) return false; 
    int sum_a = accumulate(a.begin(), a.end(), 0); 
    int sum_b = accumulate(b.begin(), b.end(), 0); 
    return sum_a/(double)a.size() < sum_b/(double)b.size(); 
} 

int main() { 
    vector<vector<int> > mat(3, vector<int>(3)); 
    mat[0][0] = 4; mat[0][1] = 5; mat[0][2] = 3; 
    mat[1][0] = 3; mat[1][1] = 2; mat[1][2] = 1; 
    mat[2][0] = 1; mat[2][1] = 8; mat[2][2] = 9; 
    sort(mat.begin(), mat.end(), comp); 
    return 0; 
} 

我不知道来处理空载体的最好办法，所以我只是让它返回false。当然，你可以给comp()一个更有意义的名字。

编辑：我认为更好的方式来处理零大小的矢量是倍增，

bool comp(vector<int> a, vector<int> b) { 
    int sum_a = accumulate(a.begin(), a.end(), 0); 
    int sum_b = accumulate(b.begin(), b.end(), 0); 
    return sum_a * b.size() < sum_b * a.size(); 
} 

Answer 4

把排在一个多重和重载<操作。这里有一个1D例如：

http://bytes.com/topic/c/answers/171028-multiset-example