c++ - 在 C/C++ 中按递增值对二维数组进行排序；知道排序后的原始位置？

Question

我已经编写了一个按递增值对二维数组进行排序的程序。

这是我的输入和输出。

Input:<p></p>

<p>Array2D[0][0] = 99 
Array2D[0][1] = 10 
Array2D[0][2] = 97 
Array2D[0][3] = 10 
Array2D[0][4] = 14 
Array2D[1][0] = 73 
Array2D[1][1] = 53 
Array2D[1][2] = 81 
Array2D[1][3] = 22 
Array2D[1][4] = 88 </p>

<p>Output:</p>

<p>Array2D[0][0] = 10 
Array2D[0][1] = 22 
Array2D[0][2] = 53 
Array2D[0][3] = 53 
Array2D[0][4] = 73 
Array2D[1][0] = 73 
Array2D[1][1] = 81 
Array2D[1][2] = 81 
Array2D[1][3] = 88 
Array2D[1][4] = 99 
</p>

现在，我想知道的是值(value)观的原始位置。例如。 Array2D[0][0] 现在包含 10，但我也想知道这个 10 之前在输入中的位置，例如，它在输入中的 Array2D[0][3] 中。所以，我想要所有值的原始位置。

我不知道该怎么做。也许使用一些额外的结构来记住位置或使用指针。任何帮助将不胜感激。

可以用C、C++实现。

注意:对于排序，我将二维数组转换为一维数组，并使用冒泡排序对其进行排序，然后转换回二维数组。

Answer 1

一种简单的方法是，不是只在原始 Array2D 中存储值，而是存储一个小结构:

struct {
    int value;
    int position;
};

在对数组进行排序之前，您将位置存储在 position 变量中。要获得完整的解决方案，请尝试这样的事情:

struct Element {
    Element() {}
    Element(int value) : value(value) {}
    bool operator < (const Element& rhs) const {return value < rhs.value;}
    int value;
    int position;
};

Element Array2D[2][5];
Array2D[0][0] = 99;
Array2D[0][1] = 10;
Array2D[0][2] = 97;
Array2D[0][3] = 10;
Array2D[0][4] = 14;
Array2D[1][0] = 73;
Array2D[1][1] = 53;
Array2D[1][2] = 81;
Array2D[1][3] = 22;
Array2D[1][4] = 88;
int elementCount = sizeof(Array2D) / sizeof(Element);
for (int i = 0; i < elementCount; ++i) {
    (&Array2D[0][0])[i].position = i;
}
std::stable_sort(&Array[0][0], &Array[0][0] + elementCount);