使用下标对数组进行排序而不移动数组元素

Question

我必须使用C中的mergesort对一个非负ints数组进行排序，但是有一个陷阱--我不能在实际的数组元素周围移动，比如如果我有{3,5,6,7,0,4,1,2}，那么所需的输出应该是

第一个元素位于下标:4。

0 3 5

1 5 2

2 6 3

3 7 -1

4 0 6

5 4 1

6 1 7

7 2 0

查看原始输入的顺序如何保持不变，但只有键在比较数字时才被交换？到目前为止，我的主要职能是：

void Merge(int *A,int *L,int leftCount,int *R,int rightCount) 

{

    int i,j,k;

    // i - to mark the index of left sub-array (L)
    // j - to mark the index of right sub-array (R)
    // k - to mark the index of merged sub-array (A)
    i = 0; j = 0; k =0;

    while(i<leftCount && j< rightCount)
    {
        if(L[i]  <=  R[j])
        {
            //something important;
             i++;
        }
        else
        {
            //something important;
            j++;
        }
    }

    i=0;
    j=0;
    while(i < leftCount) A[k++] = L[i++]; //merge all input sequences without swapping initial order

    while(j < rightCount) A[k++] = R[j++];

}

// Recursive function to sort an array of integers.
void MergeSort(int *A,int n) 

{

    int mid,i,k, *L, *R;

    if(n < 2)
    {
       return; 
    }


    mid = n/2;  // find the mid index.

    // create left and right subarrays
    // mid elements (from index 0 till mid-1) should be part of left sub-array
    // and (n-mid) elements (from mid to n-1) will be part of right sub-array
    L = (int*)malloc(mid*sizeof(int));
    R = (int*)malloc((n- mid)*sizeof(int));

    for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray
    for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray

    MergeSort(L,mid);  // sorting the left subarray
    MergeSort(R,n-mid);  // sorting the right subarray
    Merge(A,L,mid,R,n-mid);  // Merging L and R into A as sorted list.
        free(L);
        free(R);
}

我知道，当合并排序过程中只有单个元素时，必须将递归树底部的所有元素的索引初始化为-1。然后，在比较左数组和右数组的数组元素时，我必须相应地更改这些索引。但那是我卡住的地方。我的教授告诉全班要使用链接列表，但我很难想象如何实现链接列表来实现这种索引。我不想让别人做我的家庭作业，我只想让别人用伪代码来解释我该怎么做，然后我就可以自己写实际的代码了。但是我太迷茫了，如果这个问题问得很糟糕，我很抱歉，但是我在这里打了一个新的屁股，我吓坏了。

Answer 1

创建一个链接的项列表，其中每个列表项都具有每个数组项的值和索引。因此，除了prev/next之外，链接列表中的每个项都是一个具有struct成员uint value;和uint index;的结构。

仅通过迭代数组和每个数组元素，预先填充链接列表，并在每个链接列表项中添加一个新的链接列表项，并在每个链接列表项中设置数组元素的值和索引。

使用预填充的链接列表作为实际数组值的“代理”，并对链接列表进行排序，就好像它是原始数组一样。也就是说，不是基于myArray[i]的排序，而是基于currentLinkListItem.value的排序。

Answer 2

说到相互关联的清单：

typedef struct ValueNode
{
    struct ValueNode* next;
    int* value;
} ValueNode;

typedef struct ListNode
{
    struct ListNode* next;
    ValueNode* value;
} ListNode;

单链表就足够了..。

首先是合并算法：

ValueNode* merge(ValueNode* x, ValueNode* y)
{
    // just assuming both are != NULL...
    ValueNode dummy;
    ValueNode* xy = &dummy;
    while(x && y)
    {
        ValueNode** min = *x->value < *y->value ? &x : &y;
        xy->next = *min;
        *min = (*min)->next;
        xy = xy->next;
    }
    // just append the rest of the lists - if any...
    if(x)
    {
        xy->next = x;
    }
    else if(y)
    {
        xy->next = y;
    }
    return dummy.next;
}

假人只是因为不必在循环中检查for NULL .

现在让我们使用它：

int array[] = { 3, 5, 6, 7, 0, 4, 1, 2 };
ListNode head;
ListNode* tmp = &head;
for(unsigned int i = 0; i < sizeof(array)/sizeof(*array); ++i)
{
    // skipping the normally obligatory tests for result being 0...
    ValueNode* node = (ValueNode*) malloc(sizeof(ValueNode));
    node->value = array + i;
    node->next = NULL;
    tmp->next = (ListNode*) malloc(sizeof(ListNode));
    tmp = tmp->next;
    tmp->value = node;
}
tmp->next = NULL;

现在我们已经设置了一个列表，每个列表都包含一个元素。现在，我们对两个后续列表进行合并。我们需要注意:如果我们将两个列表合并为一个，保持它作为新的头，将下一个列表合并到其中，等等，那么我们就实现了选择排序！因此，我们需要确保在所有其他数组被合并之前，我们没有接触到已经合并的数组。所以下一步看起来有点复杂..。

while(head.next->next) // more than one single list element?
{
    tmp = head.next;
    while(tmp)
    {
        ListNode* next = tmp->next;
        if(next)
        {
            // we keep the merged list in the current node:
            tmp->value = merge(tmp->value, next->value);
            // and remove the subsequent node from it:
            tmp->next = next->next;
            free(next);
        }
        // this is the important step:
        // tmp contains an already merged list
        // -> we need to go on with the NEXT pair!
        tmp = tmp->next;
        // additionally, if we have an odd number of lists,
        // thus at the end no next any more, we set tmp to NULL,
        // too, so we will leave the loop in both cases...
    }
}

最后，我们可以打印结果；请注意，在您的外部链接列表中只剩下一个链接列表：

ValueNode* temp = head.next->value;
while(temp)
{
    printf("%d\n", *temp->value);
    temp = temp->next;
}

现在还缺的是释放分配的内存-我会留给你的.