-3

我正在尝试解决一个问题，例如...在数组中，我们必须将所有奇数元素移到开头...偶数元素到结尾...我尝试过这种方式，但是偶数在这里失去了顺序...可以谁来帮帮我 ？？？？？？？我得到的输出是 ...1 3 5 7 9 4 8 2 6
期望线性时间解决方案...

 #include<stdio.h>
 void swap(int *p,int *q)
 {
 *p=*p^*q;
  *q=*p^*q;
  *p=*p^*q;
 }
  int main()
  {
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int  odd=0;
  int even=0;
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  while(even< arr_size){
     if(arr[even]&1)
        swap(&arr[odd++],&arr[even++]);
     else
        even++;
  }
 int i=0;
 for(i=0;i<arr_size ;i++)
 printf("%d  ",arr[i]);
 return 0;
}
4

3 回答 3

2

您可以使用qsort带有特殊比较功能的调用：

#include <stdio.h>
#include <stdlib.h>

int cmp(const void * a, const void * b) {
    int aa = *((int*)a);
    int bb = *((int*)b);
    // If aa is odd and bb is even aa is smaller
    if(aa%2 == 1 && bb%2 == 0)
        return -1;
    // If bb is odd and aa is even bb is smaller
    if(aa%2 == 0 && bb%2 == 1)
        return 1;
    // If both even or odd respect current position. (If a is before b in arr a has lower address)
    if(a<b)
        return -1;
    return 1;
}
int main(void) {
    int arr[] = { 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};    
    int len = sizeof(arr)/sizeof(arr[0]);
    int i;
    qsort(arr, len, sizeof(int), cmp);
    for(i=0; i<len; i++)
        printf("%d ", arr[i]);
    return 0;
}

对于不使用辅助数组的解决方案（如HussainAl-Mutawa所做的那样），您可以使用一种插入排序来获得就地解决方案，但它的运行时间是二次增长的，因此HussainAl-Mutawa的版本似乎是最佳的，如果运行时是首选:)。只是为了完整起见，我的实现：

int main(void) {
    int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
    int len = sizeof(arr)/sizeof(arr[0]);
    int i,j;
    for(i=1; i<len; i++) {
        int cur=arr[i];
        if(cur%2 == 0)
            continue;
        j=i;
        while(j>0 && arr[j-1]%2 == 0) {
           arr[j]=arr[j-1];
           j--;
        }
        arr[j]=cur;
    }

    for(i=0; i<len; i++)
        printf("%d ", arr[i]);

    return 0;
}
于 2012-09-29T06:37:24.773 回答
2

这个解决方案怎么样

#include<stdio.h>


  int main()
  {
  int i;
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  int sorted[arr_size];
  int sp = 0;
  for(i=0;i<arr_size;i++){
     if(arr[i]&1){
        sorted[sp++]=arr[i];
     }
  }

  for(i=0;i<arr_size;i++){
     if(!(arr[i]&1)){
        sorted[sp++]=arr[i];
     }
  }

  for(i=0;i< arr_size ;i++)
    printf("%d  ", sorted[i]);
 return 0;
}

输出是

 1  3  5  7  9  2  4  6  8

** 更新 **

虽然上面使用了更多空间并在列表上运行了两次，但以下内容只在列表上运行了一次，但仍然使用更多空间

 int main(){

  int i;
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  int sorted[arr_size];
  int even = 1+arr_size/2;
  int odd  = 0;

  for(i=0;i<arr_size;i++){
     if(arr[i]&1)
        sorted[odd++]=arr[i];
     else
        sorted[even++]=arr[i];
  }

  for(i=0;i< arr_size ;i++)
    printf("%d  ", sorted[i]);

 return 0;
}
于 2012-09-29T06:56:09.673 回答
-1

如果交换不是比这更重要的，您可以简单地创建两个 for 循环，一个用于添加偶数，另一个用于赔率。像这样的东西： -

  j=0;
  for(i=2;i<a_size;i+2)
  {
     b[j++]=a[i];
  }
  for(i=1;i<a_size;i+2)
  {
     b[j++]=a[i];
  }

并在最后打印一个。

于 2012-09-29T06:21:34.017 回答