根据给定的索引重新排序数组

Question

算法根据给定索引重新排序数组

a[] = [50, 40, 70, 60, 90]
 index[] = [3,  0,  4,  1,  2]
a= [60,50,90,40,70] 

在O（n）和没有额外的数组/空格

Answer 1

你需要一个临时变量和循环计数器/索引的空间。根据算法通常的“重新排序”也将把index []改回{0,1,2,3,4}。

提示，注意index []中索引的排序。

          {0, 1, 2, 3, 4}
index[] = {3, 0, 4, 1, 2}

可以通过遵循“循环”来完成重新排序。从索引[0]开始，如果查看索引[0]，则注意“周期”，然后索引[索引[0]]，依此类推......

// 1st cycle
index[0] == 3   // cycle starts at 0
index[3] == 1
index[1] == 0   // end of cycle since back at 0

// 2nd cycle
index[2] == 4   // cycle starts at 2
index[4] == 2   // end of cycle since back at 2

示例C代码：

#include <stdio.h>

static int A[] = {50, 40, 70, 60, 90};
static int I[]  = {3,  0,  4,  1,  2};

int main()
{
int i, j, k;
int tA;
    /* reorder A according to I */
    /* every move puts an element into place */
    /* time complexity is O(n) */
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            tA = A[i];
            j = i;
            while(i != (k = I[j])){
                A[j] = A[k];
                I[j] = j;
                j = k;
            }
            A[j] = tA;
            I[j] = j;
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        printf("%d\n", A[i]);
    return 0;
}

相同的算法，但使用交换而不是移动（这是较慢的方法）。

#include <stdio.h>

#define swap(a, b) {(a)^=(b); (b)^=(a); (a)^=(b);}

static int A[] = {50, 40, 70, 60, 90};
static int I[]  = {3,  0,  4,  1,  2};

int main()
{
int i, j, k;
    /* reorder A according to I */
    /* every swap puts an element into place */
    /* last swap of a cycle puts both elements into place */
    /* time complexity is O(n) */
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            j = i;
            while(i != (k = I[j])){
                swap(A[j], A[k]);
                I[j] = j;
                j = k;
            }
            I[j] = j;
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        printf("%d\n", A[i]);
    return 0;
}