冒泡排序算法详解

2017-04-23 20:46 阅读 535 次 评论 0 条

单向冒泡排序算法

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*/

 

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:冒泡排序算法详解 | 猿笔记
分类:JAVA, 程序笔记 标签:,

发表评论


表情