单向冒泡排序算法
1、从上向下冒泡的冒泡排序的基本思想是：
（1）首先将第一个记录的关键字和第二个记录的关键字进行比较，若为“逆序”（即L.r[1].key>L.r[2].key），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录的关键字和第n个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上；
（2）然后进行第二趟冒泡排序，对前面的n-1个记录进行同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置；
一般地，第i趟冒泡排序是从L.r[1]到L.r[n-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需要进行K(1≤k<n)趟冒泡排序，显然，判别冒泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。
算法描述如下：
void bibubble1(int r[],int n)
{
int flag=1;
int i=0,j;
int temp;
while(flag==1)
{
flag=0;
for(j=i+1;j<n-i-1;j++)
if(r[j]>r[j+1])
{
flag=1;
temp=r[j];r[j]=r[j+1];r[j+1]=temp;
}
i++;
}
}
2、从下向上冒泡的冒泡排序的基本思想是：
（1）首先将第n-1个记录的关键字和第n个记录的关键字进行比较，若为“逆序”（即L.r[n].key<L.r[n-1].key），则将两个记录交换之，然后比较第n-2个记录和第n-1个记录的关键字。依次类推，直至第1个记录的关键字和第2个记录的关键字比较过为止。这是第一趟起泡排序，其结果是使得关键字最小的记录被安置到第一个记录的位置上；
（2）然后进行第二趟起泡排序，对后面的n-1个记录进行同样的操作，其结果是使关键字次小的记录被安置到第2个记录的位置；
一般地，第i趟起泡排序是从L.r[n] 到L.r[i]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最小的记录被交换到第i的位置上。整个排序过程需要进行K(1≤k<n)趟起泡排序，显然，判别起泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。
算法描述如下：
void bibubble2(int r[],int n)
{
int flag=1;
int i=0,j;
int temp;
while(flag==1)
{
flag=0;
for(j=n-i-1;j>=i+1;j--)
if(r[j]<r[j-1])
{
flag=1;
temp=r[j];r[j]=r[j-1];r[j-1]=temp;
}
i++;
}
}
双向冒泡排序算法
双向冒泡排序的基本思想是：
1、首先将第一个记录的关键字和第二个记录的关键字进行比较，若为“逆序”（即L.r[1].key>L.r[2].key），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录的关键字和第n个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上；
2、然后进行第二趟冒泡排序，将第n-2个记录的关键字和第n-1个记录的关键字进行比较，若为“逆序”（即L.r[n-1].key<L.r[n-2].key），则将两个记录交换之，然后比较第n-3个记录和第n-2个记录的关键字。依次类推，直至第1个记录的关键字和第2个记录的关键字比较过为止。其结果是使得关键字最小的记录被安置到第一个记录的位置上；
3、再对其余的n-2个记录进行上述（1、2）同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置，使关键字次小的记录被安置到第2个记录的位置；
一般地，第i趟冒泡排序是：若i为奇数，则从L.r[i/2 +1]到L.r[n-i/2]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i/2的位置上；若i为偶数，则从L.r[n-i/2]到L.r[i/2]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最小的记录被交换到第i/2的位置上。整个排序过程需要进行K(1≤k<n)趟冒泡排序，同样，判别冒泡排序结束的条件仍然是“在一趟排序过程中没有进行过交换记录的操作”。
算法描述如下：
void bibubble3(int r[ ],int n)/*相邻两趟是反方向起泡的冒泡排序算法*/
{
int j,low,high,temp;
int flag=1;
low=0;high=n-1; /*冒泡的上下界*/
while(low<high&&flag)
{
flag=0;
for(j=low;j<high;j++) /*从上向下冒泡*/
if(r[j]>r[j+1])
{
temp=r[j];r[j]=r[j+1];r[j+1]=temp;
flag =1;
}
high--; /*修改上界 */
for(j=high;j>low;j--) /*从下向上冒泡*/
if(r[j]<r[j-1])
{
temp=r[j];r[j]=r[j-1];r[j-1]=temp;
flag =1;
}
low++; /*修改下界*/
}/*while*/
}/* bibubble3*/
对上述算法进行化简,循环体中只包含一次冒泡的算法描述如下：
void bibubble4(int r[ ],int n)/*循环体中只包含一次冒泡的双向冒泡排序*/
{
int j,temp,b[3]; /*b[0]为冒泡的下界,b[2]为上界,b[1]无用*/
int d=1;
int flag=1;
b[0]=0;b[ 2 ]=n-1; /*d为冒泡方向的标识,1为向上,-1为向下*/
while(b[0]<b[2]&&flag)
{
flag=0;
for(j=b[1-d];j!=b[1+d];j+=d) /*统一的冒泡算法*/
if((r[j]-r[j+d])*d>0) /*注意这个交换条件*/
{
temp=r[j];r[j]=r[j+d];r[j+d]=temp;
flag=1;
}
b[1+d]-=d; /*修改边界*/
d*=-1; /*换个方向*/
}/*while*/
}/*bibubble4*/
声明一下:我不是原创..版权归原创所有哦
