如何网络销售水果:冒泡排序法

以数组中的10个数从小到大升序排序为例.

第一个程序,大家都会的:

main()
{
int a[10];
int i,j;
for(i=0;i<10;i++)a[i]=9-i;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(a[j]>a[j+1])
{
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
for(i=0;i<10;i++)
printf("\n%d",a[i]);
}

第二个程序,内循环次数减小了:

main()
{
int a[10];
int i,j;
for(i=0;i<10;i++)a[i]=9-i;
for(i=0;i<9;i++)
for(j=0;j<9-i;j++)
if(a[j]>a[j+1])
{
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
for(i=0;i<10;i++)
printf("\n%d",a[i]);
}

第三个程序,内循环次数再一次减少:

main()
{
int a[10];
int i,j,p;
for(i=0;i<10;i++)a[i]=9-i;
for(i=9;i>0;i=p)
for(j=p=0;j<i;j++)
if(a[j]>a[j+1])
{
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
p=j;
}
for(i=0;i<10;i++)
printf("\n%d",a[i]);
}

对于我们这个特定的10个数来说,三个程序的执行是一样的,但是如果要排序的内容有很多是已经符合要求顺序的,尤其是只有少量数据需要重新排序的时候,这三个程序的优劣是很明显的.

基本算法就是用所要排序数组中的每个元素与所有元素进行比较遇到比当前元素大的或小的，就进行交换;

bubblesort(struct rec r[],int n)
{
int i,j;
struct rec w;
unsigned long int compare=0,move=0;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
{
if(r[j].key<r[j-1].key)
{
w=r[j];
r[j]=r[j-1];
r[j-1]=w;
move=move+3;
}
compare++;
}
printf("\nBubbleSort compare= %ld,move= %ld\n",compare,move);
}

如果有N个数进行排序，循环N-1次，每次循环从头按序两两比较，按照排序要求进行互换，直到结束进行下次循环……

总是相邻的两个数之间进行比较，就像前（后）空翻一样。