c - 调整数组中的位置以保持递增顺序

Question

我在C语言中的逻辑创建中遇到了一个问题。我要做的是:

1)我有数组a[215] = {0,1,2,3,4,5}。现在我必须添加该数组的两个最小元素，然后定位新的元素在同一数组中获得的元素，使其保持数组的递增顺序(a[]，已经排序的数组)。

(2)还要注意添加的最小的两个元素不能再次参与排序和加法，如果已经添加了就必须固定一次位置，但是新加法得到的元素可以参加另外并再次排序。例如:我们将两个最小元素0和1相加，0+1=1，所以“1”就是相加的结果，现在这个“1”必须定位在a中[] 这样仍然应该有递增的顺序。所以:

0 1 1(added here) 2 3 4 5

现在我们必须再次找到最小的两个节点(请再次阅读注释(2)以便更好地理解)。我们不能再次添加0 abnd 1，因为它们已经参与了加法。所以这次我们将添加 1 和 2(这个位于索引 3 处，请不要与索引 2 处的那个混淆)。所以我们得到1+2=3

0 1 1 2 3 3 4 5 我们再次定位 3 以维持递增顺序。我们再次重复:对于索引 4 和 5 处的元素(因为我们已经对索引 0,1 和 2,3 处的元素进行了加法)，我们将得到 3+3=6，再次将其放置在一个[]。

0 1 1 2 3 3 4 5 6 这次 6 大于 4 和 5，因此它将出现在 5 之后以保持递增顺序。

At last we will get a[] like this:
a[ ]= [0 1 1 2 3 3  4 5 6 9 15].

所以加法保持在索引 0,1 和 2,3 和 4,5 和 6, 7 和 8,9 之间，最后我们有 15，这是最后一个，所以我们在这里停止。

现在来看看我已经实现了多少:我已经实现了这个加法部分，它对数组 a[ ] = [0 1 2 3 4 5] 进行加法。并将新获取的元素放在最后一个索引处(在我的代码中为dataSize，请参见data[dataSize++]=newItem)。

每次我调用函数 PositionAdjustOfNewItem(data,dataSize); 时，都会将数组(还包含最后一个索引处新获得的元素)作为第一个参数，将新获得的大小作为第二个参数。下面是代码:

for(i=0;i<14;i++)
   for(j=1;j<15;j++)
   { 
      // This freq contains the given array (say a[]=[0 1 2 3 4 5] in our case and
      // it is inside the struct Array { int freq}; Array data[256]; )
      newItem.freq = data[i].freq + data[j].freq;
      data[dataSize++]=newItem;
      PositionAdjustOfNewItem(data,dataSize);  // Logic of this function I am not able to develop yet. Please help me here
      i=i+2; 
      j=j+1;
   }

我无法实现函数 PositionAdjustOfNewItem() 的逻辑，该函数传递数组 data[]，其中包含所有元素和最后一个索引处新添加的元素，在第二个参数中我传递新获得的元素将新获得的元素放入最后一个索引后的数组大小。每次当我添加两个元素时，我都会调用 PositionAdjustOfNewItem() 传递最后添加的元素和新获得的大小。应该通过此函数 PositionAdjustOfNewItem() 进行排序。

这个 PositionAdjustOfNewItem() 的复杂性尽可能低。代码上面的部分只是为了让你了解我用来添加元素的机制，你在那里没什么可做的，我需要您的帮助仅在于获取 PositionAdjustOfNewItem() 的逻辑。(即使我已经用 qsort() 完成了它，但复杂性非常高)。那么还需要其他方式吗？

Answer 1

像这样怎么样:

注意:在您的示例中，您正在处理具有 freq 作为字段的某种结构的数组。在我的示例中，我使用简单的整数数组。

#include <stdio.h>
#include <string.h>

int a[] = {0,1,2,3,4,5};

int main(void) {
  int i,j;
  // Initialize a new array big enough to hold the result.
  int* array = new int[15];
  memcpy(array, a, 6*sizeof(int));
  int length=6;

  // Loop over consecutive indeces.
  for (i=0; i+1<length; i+=2) {
    // Get the sum of these two indeces.
    int sum=array[i]+array[i+1];

    // Insert the sum in the array, shifting elements where necessary.
    for (j=length-1; j>i+1; j--) { 
      if (sum >= array[j]) {
        // Insert here
        break;
      } else {
        // Shift
        array[j+1]=array[j];
      }
    }
    array[j+1]=sum;
    // We now have one more element in the array
    length++;
  }

  // Display the array.
  printf("{ ");
  for (j=0; j<length; j++) {
    printf("%d ", array[j]);
  }
  printf("}\n");
}

要插入总和，我们需要从头到尾遍历数组，寻找它所属的位置。如果我们遇到一个小于总和的值，那么我们只需将其插入到该值之后即可。否则(即值大于总和)，我们需要将其插入之前。因此，需要将该值移高一位，然后检查之前的值。继续，直到找到位置。

如果您只需要 PositionAdjustNewItem 方法，则如下所示:

void PositionAdjustOfNewItem(int* array, int length) {
  int newItem = array[length-1];
  for (int j=length-2; j>i+1; j--) { 
    if (sum >= array[j]) {
      // Insert here
      break;
    } else {
      // Shift
      array[j+1]=array[j];
    }
  }
  array[j+1]=sum;
}

当您运行它时，它会产生您期望的输出。

$ ./a.out
{ 0 1 1 2 3 3 4 5 6 9 15 }