第2題
(1)排序結束的最基本即最保守的條件是:進行n次奇偶交換操作。
還有壹個是針對本來就基本有序的情況,如果在n次循環中,有兩次沒有交換操作,則停止排序,因為此時必有序!
故綜合起來為:當有兩次沒有交換操作或進行了n次奇偶交換時,排序結束。
(2)源代碼
#include<iostream>
#include<string>
using namespace std;
void OddEvenSort(int* p,const int& size)
{
int k=-1;
for(int i=0;i<size;++i)
{
int j=i%2;
for(;j<size;j+=2)
if(j+1<size&&p[j]>p[j+1])
{
++k;
p[j]=p[j+1]^p[j] , p[j+1]=p[j]^p[j+1] , p[j]=p[j+1]^p[j] ;//交換
}
if(i-k==2)
break;//兩次沒有交換,排序停止
}
}
void PrintArray(int* p,const int& size)
{
for(int i=0;i<size;++i)
{
cout<<p[i]<<'\t';
if((i+1)%8==0)
cout<<endl;
}
cout<<endl;
}
void main()
{
int size=0;
int *p=0;
cout<<"Enter the size of an array!"<<endl;
cin>>size;
p=new int[size];
cout<<"Please input the elements!"<<endl;
for(int i=0;i<size;++i)
cin>>p[i];
OddEvenSort(p,size);
cout<<"After the sortion,the array is:"<<endl;
PrintArray(p,size);
delete[] p;
}