在C语言中按照索引数组对数组进行排序

Question

可能是重复问题：
原地数组重排序？

我有一个包含结构的未排序原始数组，如下所示：

{D, A, B, E, C}

并且原始数组的索引数组按照排序顺序排列：

{2, 3, 5, 1, 4} // Edited. Then I get {A, B, C, D, E}.

我该如何使用一个索引数组简单地重新排列原始数组？

我不能通过索引位置创建新的数组并插入元素。

- Peter K.

---

人们，他不是想要对数组进行排序。他想通过第二个数组的索引值重新排列它，而不需要使用中间数组。 - WhozCraig

注意C语言使用从0开始的索引，因此索引数组应该是{1,2,4,0,3}。 - wildplasser

当我完成这个有趣的家庭作业时，我其实很享受 - 有没有同学可以分享一些关于这个的想法？ - user166390

这个问题以前已经被问过和回答了很多次。我在上面发布了一个链接，但还有许多其他的答案。 - AnT stands with Russia

@texasbruce：不，它并不是。相反，将无关和/或临时数据挤在一起成为一个结构体将是设计上的失误。这里所请求的是一个经典方法，例如当需要按一个特定键数组对多个独立数组进行排序时。正确的方法是从键数组中生成排序置换（即从键数组中“提取”排序信息），然后将该置换“应用”于所有其他数组。OP的问题是有关“应用”置换的正确技巧。这是一个经典的编程问题。 - AnT stands with Russia

Answer 1

我的看法：

int new_i;
for (int i = 0; i < arr_size-1; ++i)
{
    while ((new_i = index_arr[i]-1) != i)
    {
        std::swap(struct_arr[i], struct_arr[new_i]);
        std::swap(index_arr[i], index_arr[new_i]);
    }
}

- panda-34

---

问题标记为[tag:c]而不是[tag:c++]。 - Olaf Dietsche

好的，std::swap函数是微不足道的，所以请将其视为伪代码算法而非可执行代码。 - panda-34

这实际上是标准循环跟随算法的非常紧凑（而且显然正确）的实现。在上面链接的旧线程中给出的实现不那么紧凑，但更加优化（即它们复制数组元素而不是交换它们），但主要原则相同。就像所有这样的实现一样，它会破坏索引数组（或需要额外的内存来存储“标志”数组）。 - AnT stands with Russia

这似乎既正确又最优，我希望楼主将采纳答案改为这个。 - hyde

这不是问题的解决方案...而且无论如何，“new_i = index_arr[i]-1”都会导致new_i变成-1... - Asylum

Answer 2

O(N^2)解决方案：

struct S[] = {D, A, B, E, C};
int o[] = {2, 3, 5, 1, 4};
int len = 5;

for (int i=1;i<=len;++i) {
  for(int j=i-1; j<len;++j) {
    if(o[j]==i) {
      if (i!=j+1) {
        swapSArrayItems(S, j, i-1);
        swapIntArrayItems(o, j, i-1);
      }
      break;
    }
  }
}

- hyde

---

索引的作用是为了降低复杂度，而不是提高复杂度。在没有任何额外信息的情况下，数组可以在O(nlogn)的时间内进行排序。显然，解决方案需要比这更好。 - SomeWittyUsername

是的，但问题说“简单”：）。无论如何，使用给定的交换和比较函数的原地排序应该可以工作，我希望有人写一个答案。 - hyde

@icepack 至少它“工作”。这就是为什么我给它点赞的原因 :) - P.P

@KingsIndian 不需要挖苦我，我知道该承认我的错误 :) 但是对于这样的问题接受O(n^2)显然不是所需的答案。 - SomeWittyUsername

最终结果的“有序性”与此问题完全无关。问题是关于根据任意排列进行原地重新排序的。在这种情况下结果恰好是“有序”的事实，只不过是给出一个任意排列的随机属性而已。 - AnT stands with Russia

@icepack 我并不是在讽刺。能够工作的解决方案应该比不能工作的更受欢迎。OP也没有提到时间复杂度。如果以后有更好的解决方案，我也会点赞，并且其他人也会点赞，这将超过当前的解决方案。 - P.P

Answer 3

这里有一个可行的版本，但请注意它会使indices变量无效：

void sortItemsBasedOnIndices(char *items[], int indices[], size_t num)
{
    // sort them
    for (int i = 0; i < num; i++)
    {
        int newIndex = indices[i];

        // take out the item at the specified index
        char *newItem = items[newIndex];

        // take out the item in that current position
        char *oldItem = items[i];

        // swap the two items
        items[i] = newItem;
        items[newIndex] = oldItem;

        // now, tell the sorted indices the location of the old item after swap
        for (int j = i; j < num; j++)
        {
            if (indices[j] == i)
            {
                indices[j] = newIndex;
                break; // we only need the first one, so then we're done
            }
        }
    }
}

int main()
{
    char *items[] = { "D", "B", "E", "A", "C" };
    int sortedIndices[] = { 3, 1, 4, 0, 2 }; // 0-based

    int size = 5;
    sortItemsBasedOnIndices(items, sortedIndices, size);

    for (int i = 0; i < size; i++)
    {
        puts(items[i]);
    }
}

- Richard J. Ross III

---

索引的作用是为了降低复杂度，而不是提高复杂度。在没有任何额外信息的情况下，数组可以在O(nlogn)的时间内进行排序。显然，解决方案需要比冒泡排序更好。 - SomeWittyUsername

@icepack 这比冒泡排序好多了。它只迭代到必要的程度。最好情况下是O(N)，最坏情况下是O(2N)。 - Richard J. Ross III

@RichardR.RossIII 这是一个典型的冒泡排序，时间复杂度为O(n^2)。 - SomeWittyUsername

这是一个典型的优化冒泡排序。网络上有许多类似的例子。它仍然是O(n^2)。 - SomeWittyUsername

它不是O(n^2)，但也不是O(2n) :D 对于一个11元素数组，最坏情况下需要41次迭代。 - Asylum

Answer 4

#include <stdio.h>

void shuffle( char **arr, int *offs, size_t cnt);

void shuffle( char **arr, int *offs, size_t cnt)
{
unsigned idx,src,dst;

for (idx=0; idx < cnt; idx++) offs[idx] -= idx;

for (idx=0; idx < cnt; idx++) {
        if (offs[idx] == 0) continue;
        char *tmp;
        tmp = arr[idx];

        for(dst = idx; offs[dst] ; dst=src) {
                src = dst+offs[dst] ;

                arr[dst] = arr[src];
                offs[dst] = 0;
                if (offs[src] == 0 ) break;
                }

        arr[dst]=tmp;
        }
}


int main (void)
{
unsigned idx;
char *array[5] = {"D","A","B","E","C"};
int index[5] =  {1,2,4,0,3};

fprintf(stdout, "Original:\n");
for (idx=0; idx < 5; idx++) {
        fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
        }

fprintf(stdout, "Shuffle:\n");
shuffle( array, index, 5);

fprintf(stdout, "After shuffle:\n");
for (idx=0; idx < 5; idx++) {
        fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
        }

return 0;
}

更新：修复了链的末尾条件（丑陋！）

- wildplasser