数组排序（C++）

Question

我学习C++，我不得不创建数组[N] [M]，以整数来填充它，然后
"Characteristic of matrix rows is called the sum of its positive even elements. You need to sort the rows of the matrix in accordance with the growth of characteristics."

任务这是我的代码

#include "stdafx.h" 
using namespace std; 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
srand((unsigned)time(NULL)); 

int n, m; 
cout << "n = "; 
cin >> n; 
cout << "m = "; 
cin >> m; 

int ** mas = new int * [n]; 
for (int i = 0; i < n; ++i) 
{ 
    mas[i] = new int[m]; 
} 

cout << "Array:\n"; 
for (int i = 0; i < n; ++i) 
{ 
    for (int j = 0; j < m; ++j) 
    { 
     mas[i][j] = rand()%41-20; 
     cout << mas[i][j] << "\t"; 
    } 
    cout << "\n"; 
} 

double * characteristic = new double[n]; 
for (int i = 0; i < n; ++i) 
{ 
    characteristic[i] = 0; 
} 

for (int i = 0; i < n; ++i) 
{ 
    for (int j = 0; j < m; ++j) 
    { 
     if((j%2 == 0) && (mas[i][j] >= 0)) 
     { 
       characteristic[i] += mas[i][j]; 
     } 
    } 
} 

cout << "Characteristics:\n"; 
for (int i = 0; i < n; ++i) 
{ 
    cout << characteristic[i] << " "; 
} 
cout << "\n"; 

for (int i = 0; i < n - 1; ++i) 
{ 
    int min = i; 
    for (int j = i + 1; j < n; ++j) 
    { 
     if (characteristic[min] <= characteristic[j]) continue; 
     min = j; 
    } 
    if (min != i) 
    { 
     double temp = characteristic[i]; 
     characteristic[i] = characteristic[min]; 
     characteristic[min] = temp; 

     for (int k = 0; k < m; ++k) 
     { 
      int temp1 = mas[i][k]; 
      mas[i][k] = mas[min][k]; 
      mas[min][k] = temp1; 
     } 

    } 
} 

cout << "\nSorted characteristics:\n"; 
for (int i = 0; i < n; ++i) 
{ 
    cout << characteristic[i] << " "; 
} 
cout << "\n"; 

cout << "Sorted array:\n"; 
for (int i = 0; i < n; ++i) 
{ 
    for (int j = 0; j < m; ++j) 
    { 
     cout << mas[i][j] << "\t"; 
    } 
    cout << "\n"; 
} 

for (int i = 0; i < n; ++i) 
{ 
    delete [] mas[i]; 
} 
delete [] mas; 

delete [] characteristic; 

system("PAUSE"); 
return 0; 
} 

我为特性创建了另一个数组，并将它与第一个数组同时排序，但似乎我使用了太困难的方法来完成给定的任务。也许有其他方法吗？

Answer 1

@sehe给你很好的建议，但是我怀疑很多这些东西在你知道更多的C++之前是没有意义的。

这里有一个简单的改进，以消除缓慢循环：

当你做掉排掉，而不是复制它们指向的每一个值的行指针。替换此：

for (int k = 0; k < m; ++k) 
    { 
     int temp1 = mas[i][k]; 
     mas[i][k] = mas[min][k]; 
     mas[min][k] = temp1; 
    } 

有了：

int* temp1 = mas[i]; 
    mas[i] = mas[min]; 
    mas[min] = temp1; 

如果你能弄清楚如何使用内置的排序算法，这将是在此之上的另一种改进，但即使这样小的变化将获得你很多。

Answer 2

由于n，m的大小在编译时已知，因此可以使用C库中的qsort函数。

#include <stdlib.h> 

void qsort(void *base, size_t nmemb, size_t size, 
      int (*compar)(const void *, const void *)); 

哪里是compar是你写一个函数，应该把它的两个参数为指针，以矩阵的行。然后它可以计算两行的特征，并根据哪一行的特征较大返回-1,0或1。

Answer 3

您是否想要对矩阵进行排序，使用与'特性'相同的顺序？

比方说，你有C++风格的代码来计算的特点：

std::vector<double> characteristic(n, 0.0); 
std::transform(begin(mas), end(mas), begin(characteristic), sum_); 

然后，您可以对它们进行排序：

std::sort(begin(characteristic), end(characteristic)); 

或者你可以，的确排序矩阵立刻道：

std::sort(begin(mas), end(mas), [&sum_](int_vec const& a, int_vec const& b) 
     { return sum_(a)<sum_(b); }); 

编辑修复所有版本以使用正确的“特征的总和”（保留名称虽然），感谢@Adam

这里是一个完整的程序，它说明了这一点：看它Live on Coliru

#include <random> 
#include <iostream> 
#include <string> 
#include <vector> 

#include <cstdlib> 
#include <algorithm> 
#include <iterator> 

using namespace std; 

int main() 
{ 
    typedef std::vector<int> int_vec; 

    srand((unsigned)time(NULL)); 
    int n, m; 
    cout << "n = "; 
    cin >> n; 
    cout << "m = "; 
    cin >> m; 

    std::vector<int_vec> mas(n, int_vec(m)); 

    for (auto& v : mas) 
     std::for_each(begin(v), end(v), [](int& i) { i = rand()%41-20; }); 

    cout << "Array:\n"; 
    for (auto const& v : mas) 
    { 
     std::copy(begin(v), end(v), ostream_iterator<int>(cout, "\t")); 
     cout << "\n"; 
    } 

    auto sum_ = [m](int_vec const& v) { 
     double vchar = 0; 
     for (auto j = 0; j < m; j+=2) 
      if(v[j] >= 0) vchar += v[j]; 
     return vchar; 
    }; 

    std::vector<double> characteristic(n, 0.0); 
    std::transform(begin(mas), end(mas), begin(characteristic), sum_); 

    cout << "Characteristics:\n"; 
    std::copy(begin(characteristic), end(characteristic), ostream_iterator<double>(cout, " ")); 
    cout << "\n"; 

    std::sort(begin(characteristic), end(characteristic)); 

    cout << "\nSorted characteristics:\n"; 
    std::copy(begin(characteristic), end(characteristic), ostream_iterator<double>(cout, " ")); 
    cout << "\n"; 

    std::sort(begin(mas), end(mas), [&sum_](int_vec const& a, int_vec const& b) { return sum_(a)<sum_(b); }); 

    cout << "Sorted Array:\n"; 
    for (auto const& v : mas) 
    { 
     std::copy(begin(v), end(v), ostream_iterator<int>(cout, "\t")); 
     cout << "\n"; 
    } 

} 

输出示例：

n = m = Array: 
11 15 19 18 
-20 -16 2 -11 
8 2 19 8 
Characteristics: 
30 2 27 

Sorted characteristics: 
2 27 30 
Sorted Array: 
-20 -16 2 -11 
8 2 19 8 
11 15 19 18