冒泡排序算法详解
需积分: 35 181 浏览量
2013-08-06
10:45:04
上传
评论
收藏 40KB DOC 举报
冒泡排序算法详解
单向冒泡排序算法
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 ag=1;
int i=0,j;
int temp;
while(ag==1)
{
ag=0;
for(j=i+1;j<n-i-1;j++)
if(r[j]>r[j+1])
{
ag=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 ag=1;
资源评论
