我已经在C中的逻辑creation.What我要做经历一个问题是：

I have undergone one problem in C in logic creation.What i have to do is:

1）我有阵 A [215] = {0,1,2,3,4,5} 。现在我要补充这两个最小的元素数组，然后放置在相同的阵列，使得其将保持阵列的增加顺序（一个[]，将其已排序阵列）中获得的新元素。

1)I have array a[215] = {0,1,2,3,4,5}.Now i have to add two minimum elements of this array and then position the newly element obtained in the same array such that it will maintain the increasing order of the array(a[],which was already sorted array).

（2）我也有照顾两个最小的添加元素不得参与再排序和此外，他们还必须固定在其位置一次，如果他们已经加入，但新近获得通过添加元素可以参加此外，再次排序。 例如： 我们添加两个最小元素 0，1，0 + 1 = 1，所以1是由加法运算得到的结果，现在这个1 必须被定位在[]，使得仍然应该有增加的次序。 因此：

(2)I also have to take care that the two minimum added elements must not participate in sorting and addition again, they must be fixed at their position once if they are already added, but the newly obtained element by addition can participate in addition and sorting again. eg: we add two minimum element 0 and 1, 0+1=1, so "1" is the result obtained by addition, now this "1" must be positioned in a[] such that still there should be increasing order. so :

0 1 1(added here) 2 3 4 5

现在我们必须再次找到最小的两个节点（请仔细阅读评论（2）重新理解以及的）。我们不能添加 0 abnd 1 再次，因为他们已经参加了除。所以这一次，我们将增加1和2（这个人是在索引三，请不要混淆wwith一个索引二）。这样我们就得到1 + 2 = 3

Now we have to again find the minimum two nodes (please read the comment (2) again to understand well) .We cannot add 0 abnd 1 again because they have already participated in in the addition. so this time we will add 1 and 2(this one is at index three, please don't get confused wwith the one at index two). so we get 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 we again positioned 3 to maintain increasing order. we repeat again: for element at index 4 and 5(because we have already done addition for element at index 0,1 and 2,3) we will get 3+3=6, again position it in a[].

0 1 1 2 3 3 4 5 6 此时6是大于4和5，因此会出现后5维持增大的顺序

0 1 1 2 3 3 4 5 6 this time 6 is greater then 4 and 5 so it will appear after 5 to maintain increasing order.

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是最后一个，所以在这里我们停止。

so the addition held was between index 0,1 and 2,3 and 4,5 and 6, 7 and 8,9 and at last we have 15 which is last one, so here we stops.

现在来多少我已经执行的： 我已经实现这个另外的一部分，这是做加法的阵列 A [] = [0 1 2 3 4 5] 。 并把新获得的最后一个索引的元素（这是数据大小在我的code，请参阅数据[数据大小++] =的newitem）。

Now coming to how much i have already implemented : I have implemented this addition part, which do addition on array a[ ] = [0 1 2 3 4 5]. And puts the newly obtained element at last index(which is dataSize in my code, please see data[dataSize++]=newItem).

我每次调用函数 PositionAdjustOfNewItem（数据，数据大小）; 给阵列（其中还包含了新获得的元素最后指数）作为第一个参数和新获得大小为第二argument.Here低于code：

Each time i call the function PositionAdjustOfNewItem(data,dataSize); giving the array(which also contains the newly obtained element at last index)as first argument and the newly obtained size as second argument.Here is the code below:

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的逻辑（），它传递数组数据[]，它包含了所有我通过新获得的元素和新添加的元素，最后指数和第二个参数数组将新获得的最后一个元素的索引处后尺寸的。 每个当我添加两个元素的时间我把这个PositionAdjustOfNewItem（）传递最后和新获得的尺寸新添加的元素。这是应该被此函数PositionAdjustOfNewItem排序（）。

I am not able to implement the logic of function PositionAdjustOfNewItem(), which pass the array data[], which contains all the elements and the newly added element at last index and in second argument i pass the newly obtained size of array after putting the newly obtained element at last index. Each time when i add two elements i call this PositionAdjustOfNewItem() passing the newly added elements at last and newly obtained size. which is supposed to be sorted by this function PositionAdjustOfNewItem().

这PositionAdjustOfNewItem（）必须为最不复杂越好。上面的code部分只是让你知道mechanish到我在用添加的元素，你什么都没有做有的，我需要你的帮助，只有在获得PositionAdjustOfNewItem的逻辑（）。 （即使我已经用的qsort做到了（），但复杂度是非常高的）。所以需要任何其他方式？

This PositionAdjustOfNewItem() have as least complexity as possible.The part above the code was just to make you aware of mechanish i am using to add elements, You have nothing to do there, I need your help only in getting the logic of PositionAdjustOfNewItem(). (Even i already done it with qsort() but complexity is very high). so need any other way?

推荐答案

怎么是这样的：

注意：在你的榜样，你是在处理一些结构，具有频率作为一个字段的数组。在我的例子中，我使用简单的整数数组。

NOTE: In your example, you are dealing with an array of some structure which has freq as a field. In my example, I am using simple integer arrays.

#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");
}

要插入的总和，是什么做的是我们遍历从端阵列的前端，寻找它​​所属的地方。如果我们遇到一个值小于总和，那么我们只需将该值后插入。否则（即值大于总和），我们需要之前将其插入。因此，值需要移动一个位置较高的，然后我们检查previous值。继续，直到我们找到了位置。

To insert the sum, what is done is we traverse the array from the end to the front, looking for the spot it belongs. If we encounter a value less then the sum, then we simply insert it after this value. Otherwise (i.e. value is greater than the sum), we need to insert it before. Thus, the value needs to be shifted one position higher, and then we check the previous value. Continue until we find the location.

如果你只需要PositionAdjustNewItem方法，那么这就是它的样子：

If you only need the PositionAdjustNewItem method, then this is what it would look like:

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

当你运行它，它会产生你所期望的输出。

When you run it, it produces the output you expect.

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