c - 给定一个由偶数和奇数组成的数组。先对数组进行排序，然后是赔率。数字的顺序不能改变

Question

如果输入数组是 - 1,4,3,8,6,5,7 输出应该是 - 4 8 6 1 3 5 7

我有一个带有插入类型的解决方案。

void sortarrayinorder(int arr[],int size)
{
     int i,j,tem,k;
     for(i=1;i<size;i++)
     {
       for(j=0;j<i;j++)
       {
       if((arr[j]%2)!=0 && (arr[i]%2)==0)
       {
         tem=arr[j];
         arr[j]=arr[i];
         for(k =i;k>j;k--)
           arr[k]=arr[k-1];

           arr[k+1]=tem;
           }
         }
     }     
}

这个问题可以用更好的方法解决吗？我的解决方案的复杂性是 o(n2)。请提供时间复杂度较低的解决方案。不允许有额外的空间。

Answer 1

您可以在 O(n) 中使用两遍方法执行此操作，只要您被允许分配单独的输出缓冲区即可。在第一遍中，检测并复制所有偶数。在第二遍中，检测并复制所有奇数。