實驗六 指標 程式片段編程題 1. 陣列奇偶排列

陣列奇偶排列

【問題描述】
從鍵盤輸入n個整數，將奇數調整到前半部分，將偶數調整到后半部分，并分別按從小到大的順序排列后輸出，

【輸入形式】
輸入為兩行，第一行為一個整數n（0<n≤107），第二行為n個整數，

【輸出形式】
輸出為一行，為經過排列之后的n個整數，

【樣例輸入】
6
12 17 6 11 2 3

【樣例輸出】
3 11 17 2 6 12

#include  <iostream>
void  qsort(int  arr[],  int  low,  int  high);
void  Swap(int  *a,  int  *b);
void  arrange(int  a[],  int  n);
using  namespace  std;

int  main()
{
        int  n;
        cin>>n;
      
int* a=new int[n];
                                                                                              /*  生成陣列a  */
        for(int  i=0;  i<n;  i++)
        {
                cin>>a[i];
        }
      
 arrange(a,n);
                                                                                                  /*  函式呼叫  */
        for(int  i=0;  i<n;  i++)
                cout<<a[i]<<"  ";

        return  0;
}

void  arrange(int  a[],  int  n)
{
        int  *p=a,  *q=a+n-1;                                    /*  指標p指向陣列的第一個元素，  指標q指向陣列的最后一個元素  */

        while(p<q)                                                              /*  指標p從左向右尋找第一個偶數，  指標q從右向左尋找第一個奇數，將p、q所指向的元素進行交換，然后指標p、q相向移動  */
        {
                
while(*p%2==1){     
                p++;
            }
while(*q%2==0){
                q--;
            }
if(p<q){
swap(*p,*q);
p++;
q--;
}


        }

        int  m;
        if  (p==q)
                m=*p%2?(p-a):(p-a-1);
        else
                m=q-a;

        qsort(a,0,m);                                                      /*  呼叫快速排序對奇數部分排序    */
        qsort(a,m+1,n-1);                                        /*  呼叫快速排序對偶數部分排序    */

}

void  qsort(int  *p,  int  low,  int  high)
{
        if  (high<=low)  return;
        int  key=p[low];
        int  i=low,  j=high+1;
        while(1)
        {
                while(p[++i]  <  key)
                {
                        if  (i==high)  break;
                }
                while(p[--j]  >  key)
                {
                        if  (j==low)  break;
                }
                if  (i>=j)  break;
                Swap(&p[i],  &p[j]);
        }

        Swap(&p[low],  &p[j]);
        qsort(p,  low,  j-1);
        qsort(p,  j+1,  high);
}

void  Swap(int  *a,  int  *b)
{
        int  temp=*a;
        *a=*b;
        *b=temp;
}

總結：
總是有三個資料過不了，除錯發現調換奇偶的結果沒有錯，快速排序就亂了，
而快速排序是題上本來給的代碼，
后來發現是這一串代碼：

void  arrange(int  a[],  int  n)
{
        int  *p=a,  *q=a+n-1;                                    /*  指標p指向陣列的第一個元素，  指標q指向陣列的最后一個元素  */

        while(p<q)                                                              /*  指標p從左向右尋找第一個偶數，  指標q從右向左尋找第一個奇數，將p、q所指向的元素進行交換，然后指標p、q相向移動  */
        {
                
while(*p%2==1){     
                p++;
            }
while(*q%2==0){
                q--;
            }
if(p<q){
swap(*p,*q);
p++;
q--;
}


        }

        int  m;
        if  (p==q)
                m=*p%2?(p-a):(p-a-1);
        else
                m=q-a;

        qsort(a,0,m);                                                      /*  呼叫快速排序對奇數部分排序    */
        qsort(a,m+1,n-1);                                        /*  呼叫快速排序對偶數部分排序    */

}

其中的這一部分：

if(p<q){
swap(*p,*q);
p++;
q--;
}

p++和q–必須在if控制范圍之內，才能保證不多移動，呼叫快排正確，