数据结构利用冒泡排序算法进行排序.doc

利用冒泡排序算法进行排序一、 项目说明： 该算法是用来实现数据排序的。利用冒泡算法对自动生成的一百个数字进行排序，冒泡排序是一种典型的交换排序方法，基本思路是：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直到“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过排序之后，关键字最小的记录到达最上端。二、 该项目的调试环境为VisualC+,该环境的使用过程为： 如图为进入该环境所需要的步骤：该图为进入VC环境的第一步，其说明了要调试该项目所要选择的一些内容：如图二为第二步在该不中我们要选择第三个类型：如图为我们完成以上步骤后所得出的结果：下面为我所调试的项目：三、 源码分析：冒泡排序的算法过程如下： #define Max 100 void bubsort(int r,int n) /*冒泡排序*/ int i,j,k; int temp; for(i=0;ii;j-) if(rjrj-1) /*如果aj比前面aj-1的小，则交换向上浮*/ /*交换数组aj和aj-1*/ temp=rj; rj=rj-1; rj-1=temp; printf( i=%d,i);for(k=0;kn;k+) printf(%2d,rk); printf(n);该代码的实现过程就是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后直到排好。int i,u; int a100; srand(unsigned)time(NULL); FILE *fp; fp = fopen(data1.dat, w); for(i=0;i100&u999) u=rand()%1000; fprintf(fp, %d , u);/将这些整数写入到数据文件data1.dat中 fclose(fp); fp = fopen(data1.dat, r); for(i=0;i100;i+) fscanf(fp,%d,&ai);/从数据文件data1.dat中读出数据 fclose(fp);bubsort(a,100); fp = fopen(data2.dat, w); for(i=0;i100;i+) fprintf(fp,%d ,ai);/将排好序的数据序列写入写入到数据文件data2.dat中 fclose(fp);其中自动生成数字的代码为：srand(unsigned)time(NULL); fp = fopen(data1.dat, w); for(i=0;i100&uL.r2.key），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录的关键字和第n个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上；（2）然后进行第二趟冒泡排序，对前面的n-1个记录进行同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置；一般地，第i趟冒泡排序是从L.r1到L.rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需要进行K(1kn)趟冒泡排序，显然，判别冒泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。算法描述如下：void bibubble1(int r,int n) int flag=1; int i=0,j; int temp; while(flag=1) flag=0; for(j=i+1;jrj+1) flag=1; temp=rj;rj=rj+1;rj+1=temp; i+; 2、从下向上冒泡的冒泡排序的基本思想是：（1）首先将第n-1个记录的关键字和第n个记录的关键字进行比较，若为“逆序”（即L.rn.keyL.rn-1.key），则将两个记录交换之，然后比较第n-2个记录和第n-1个记录的关键字。依次类推，直至第1个记录的关键字和第2个记录的关键字比较过为止。这是第一趟起泡排序，其结果是使得关键字最小的记录被安置到第一个记录的位置上；（2）然后进行第二趟起泡排序，对后面的n-1个记录进行同样的操作，其结果是使关键字次小的记录被安置到第2个记录的位置；一般地，第i趟起泡排序是从L.rn 到L.ri依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最小的记录被交换到第i的位置上。整个排序过程需要进行K(1k=i+1;j-)if(rjL.r2.key），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录的关键字和第n个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上；2、然后进行第二趟冒泡排序，将第n-2个记录的关键字和第n-1个记录的关键字进行比较，若为“逆序”（即L.rn-1.keyL.rn-2.key），则将两个记录交换之，然后比较第n-3个记录和第n-2个记录的关键字。依次类推，直至第1个记录的关键字和第2个记录的关键字比较过为止。其结果是使得关键字最小的记录被安置到第一个记录的位置上；3、再对其余的n-2个记录进行上述（1、2）同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置，使关键字次小的记录被安置到第2个记录的位置；一般地，第i趟冒泡排序是：若i为奇数，则从L.ri/2 +1到L.rn-i/2依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i/2的位置上；若i为偶数，则从L.rn-i/2到L.ri/2依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最小的记录被交换到第i/2的位置上。整个排序过程需要进行K(1kn)趟冒泡排序，同样，判别冒泡排序结束的条件仍然是“在一趟排序过程中没有进行过交换记录的操作”。算法描述如下：void bibubble3(int r ,int n)/*相邻两趟是反方向起泡的冒泡排序算法*/ int j,low,high,temp; int flag=1; low=0;high=n-1; /*冒泡的上下界*/ while(lowhigh&flag) flag=0; for(j=low;jrj+1) temp=rj;rj=rj+1;rj+1=temp; flag =1; high-; /*修改上界 */ for(j=high;jlow;j-) /*从下向上冒泡*/ if(rjrj-1) temp=rj;rj=rj-1;rj-1=temp; flag =1; low+; /*修改下界*/ /*while*/* bibubble3*/对上述算法进行化简,循环体中只包含一次冒泡的算法描述如下：void bibubble4(int r ,int n)/*循环体中只包含一次冒泡的双向冒泡排序*/ int j,temp,b3; /*b0为冒泡的下界,b2为上界,b1无用*/ int d=1; int flag=1; b0=0;b 2 =n-1; /*d为冒泡方向的标识,1为向上,-1为向下*/ while(b00) /*注意这个交换条件*/ temp=rj;rj=rj+d;rj+d=temp; flag=1;