c++ - 如何按值对数组进行排序(排序)？ *有一个转折*

Question

我想使用 C/C++ 对数组进行升序排序。结果是一个包含元素索引的数组。每个索引对应于排序数组中的元素位置。

示例

Input:  1, 3, 4, 9, 6
Output: 1, 2, 3, 5, 4

编辑: 我正在使用 shell 排序程序。重复值索引是根据原始数组中第一个重复值任意选择的。

更新:

尽管我尽了最大的努力，我仍然无法为指针数组实现排序算法。当前示例无法编译。

有人能告诉我哪里出了问题吗？

非常感谢您的帮助!

void SortArray(int ** pArray, int ArrayLength) 
{
    int i, j, flag = 1;    // set flag to 1 to begin initial pass
    int * temp;    // holding variable orig with no *
    
    for (i = 1; (i <= ArrayLength) && flag; i++)
    {
        flag = 0;
        for (j = 0; j < (ArrayLength - 1); j++)
        {
            if (*pArray[j + 1] > *pArray[j])    // ascending order simply changes to <
            { 
                &temp = &pArray[j];    // swap elements
                &pArray[j] = &pArray[j + 1];    //the problem lies somewhere in here
                &pArray[j + 1] = &temp;
                flag = 1;    // indicates that a swap occurred.
            }
        }
    }
};

Answer 1

因为您使用的是 C++，所以我会这样做。 SortIntPointers 函数可以是任何排序算法，重要的部分是它根据指针指向的 int 对指针数组进行排序。完成后，您可以遍历指针数组并分配它们的排序索引，该索引将最终位于原始数组中的原始位置。

int* intArray; // set somewhere else
int arrayLen;  // set somewhere else  

int** pintArray = new int*[arrayLen];
for(int i = 0; i < arrayLen; ++i)
{
    pintArray[i] = &intArray[i];
}

// This function sorts the pointers according to the values they
// point to. In effect, it sorts intArray without losing the positional
// information.
SortIntPointers(pintArray, arrayLen);

// Dereference the pointers and assign their sorted position.
for(int i = 0; i < arrayLen; ++i)
{
    *pintArray[i] = i;
}

希望这已经足够清楚了。