c - 在C中按索引数组对数组进行排序

Question

可能重复：
就地数组重新排序？

我有原始的未排序数组，其结构如下：

{D, A, B, E, C}

以及按排序顺序排列的原始数组的索引数组：

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

如何通过索引数组简单地重新排列原始数组？

我无法创建新数组并按索引位置插入元素。

Answer 1

我的 5 美分：

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]);
    }
}

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;
    }
  }
}

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]);
    }
}

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;
}

更新：固定链结束条件（丑陋！）