#include <cstdlib>
#include <ctime>
using namespace std
const int MAX_SIZE=100
void partition1(int A[],int n,int first,int last,int &mid)//划分
{
int i=first,j=last,x=A[i]
while(i<j)
{
while(i<j&&A[j]%3!=0)
j--
if(i<j)
{
A[i]=A[j]i++
}
while(i<j&&A[i]%3==0)
i++
if(i<j)
{
A[j]=A[i]
j--
}
}
A[i]=x
mid=i
}
void partition2(int A[],int n,int first,int last,int &mid)//划分
{
int i=first,j=last,x=A[i]
while(i<j)
{
while(i<j&&A[j]%3!=1)
j--
if(i<j)
{
A[i]=A[j]i++
}
while(i<j&&A[i]%3==1)
i++
if(i<j)
{
A[j]=A[i]
j--
}
}
A[i]=x
mid=i
}
void QuickSort(int A[],int n,int first,int last)//快速排序
{
int middle
if(first<last)
{
partition1(A,n,first,last,middle)
partition2(A,n,middle+1,last,middle)
}
}
void display(int A[],int n)
{
int i=0
for(i=0i<ni++)
cout<<A[i]<<" "
cout<<endl
}
int main()
{
int array[MAX_SIZE],i=0,n=1
srand(time(0))
cout<<"提示:本程序是将一个整型数组调整为这样的数组:所有3的倍数在左边,所有除以 "<<endl
cout<<"3余1的数放在中间,而所有除以3余2的数放在最右边.要求算法的时间尽可能少. "<<endl
cout<<endl<<"数组中元素的值在1~n之间变化,请输入n的值:"
cin>>n
for(i=0i<MAX_SIZEi++) //插入随机数
array[i]=rand()%n
cout<<"排序前:"<<endl
display(array,MAX_SIZE)
QuickSort(array,MAX_SIZE,0,MAX_SIZE-1)
cout<<"排序后:"<<endl
display(array,MAX_SIZE)
system("PAUSE")
return 0
}
快速排序
楼主程序中调用函数cal_crc()的方式不正确。函数cal_crc()用于计算输入串的校验码,因此函数输入参数包含输入串及该串的长度。建议将main()函数修改为:
#include <string.h>
void main()
{
unsigned char buf[] = "ABCDEFG1234567"// 输入串
unsigned char len = 14// 输入串的长度
unsigned int crc
crc = cal_crc(buf, len)
}
最后需要注意的是,输入串的长度不能大于256个字节。上述例子程序中假定了输入串为字符串,实际上,还可以是字节串,此时变量len表示字节串的包含的字节个数。