c - 在 C 中对数组进行排序而不丢失原始索引

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 7 年前。

Improve this question

我正在开发一个函数，该函数获取数组并对它进行排序而不丢失原始索引，例如:

    originalArray[5] = {9, 2, 3, 4, 15};
    // code
    // ..

结果:

sortedArr[5] = {2, 3, 4, 9, 15};
index[5] = {1, 2, 3, 0, 4};

注意如何

/*
index[0] == 1 because sortedArr[0] == originalArr[1]
index[3] == 0 because sortedArr[3] == originalArr[0]
index[4] == 4 because sortedArr[4] == originalArr[4]
*/

等等，重点是保存数字的索引，以便我可以在另一个函数中使用它们。在示例中，我制作了两个数组(已排序和原始)，它应该与我制作的数组相同，只是为了解释我的观点。时间复杂度应限制为 O(n*log(n))。 n表示数组的大小，(最大为100)。

推荐(老师给我们推荐的)使用签名的函数

void rem_sort(int array[], int index[], int size)

。编辑:所以每个人都在问我到目前为止我尝试过什么，如果这可以帮助你帮助我，很抱歉我没有先提到它，无论如何这是我到目前为止尝试过的，首先我尝试对我成功了，但我丢失了原始数组的索引，这不是我的观点，所以我想如果我创建一个新的“临时”数组并将原始数组复制到其中并以这种方式对其进行排序，我不会影响我的原始数组，但我无法获得正确的索引(具有这种复杂性)，我考虑过使用指针，但我不知道该怎么做，所以我被困住了!

感谢您的帮助!

Answer 1

由于这是 C 而不是 C++，因此您需要创建自己的排序程序，因为我认为 qsort() 可能是 O(n^2) 最坏的情况。

由于您将使用自己的排序程序，因此您可以同时对数组和索引进行排序，将它们视为元素对。

如果有一个可以调用的现有 O(n log(n)) 排序函数，您可以创建一个索引从 0 到 length-1 的数组，并根据该数组对索引数组进行排序，然后复制根据排序后的索引将数组复制到临时数组，然后将临时数组复制回原始数组。

void rem_sort(int array[], int index[], int size){
    /* temp array */
    int * tmpa = malloc(size * sizeof(array[0]));
    int i;
    /* generate indices to array */
    for(i = 0; i < size; i++)
        index[i] = i;
    /* sort index according to array in O(n log(n)) time */
    sort(array, index, size);
    /* tmpa[] = sorted array[] */
    for(i = 0; i < size; i++)
        tmpa[i] = array[index[i]];
    /* copy tmpa to array */
    for(i = 0; i < size; i++)
        array[i] = tmpa[i];
    free(tmpa);
    return;
}