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