-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

** アップデート **

上記はより多くのスペースを使用し、リストを 2 回実行しますが、以下はリストを 1 回だけ実行しますが、それでもより多くのスペースを使用します

 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

スワッピングがこれよりも対等でない場合は、偶数を追加するためとオッズを追加するための 2 つの 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 に答える