冒泡排序算法及各种程序示例.docx
《冒泡排序算法及各种程序示例.docx》由会员分享，可在线阅读，更多相关《冒泡排序算法及各种程序示例.docx（19页珍藏版）》请在冰点文库上搜索。
冒泡排序算法及各种程序示例
冒泡排序（BubbleSort）的基本概念是：
依次比较相邻的两个数，将小数放在前面，大数放在后面。
即在第一趟：
首先比较第1个和第2个数，将小数放前，大数放后。
然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
至此第一趟结束，将最大的数放到了最后。
在第二趟：
仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。
外循环重复9次，内循环依次重复9，8，…，1次。
每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,…,9，对于每一个i,j的值依次为1,2,…10-i。
在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而倍受青睐。
设想被排序的数组R[1..N]垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上”漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
若记录序列的初始状态为”正序”，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为”逆序”，则需进行n（n-1）/2次比较和记录移动。
因此冒泡排序总的时间复杂度为O（n*n）。
冒泡排序法存在的不足及改进方法：
第一，在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志单元flag，将其设置为OFF，表示被排序的表示是一个无序的表。
在每一排序开始时，检查此标志，若此标志为0，则结束排序；否则进行排序；
第二，当排序的数据比较多时排序的时间会明显延长。
改进方法：
快速排序：
具体做法：
任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完
局部冒泡排序算法对冒泡排序的改进：
在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。
为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。
局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。
由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。
程序示例
DELPHI
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797
ProcedureBubbleSort（VarR:
FileType）//从下往上扫描的起泡排序//
Begin
ForI:
=1ToN-1Do//做N-1趟排序//
begin
NoSwap:
=True;//置未排序的标志//
ForJ:
=N–1DownTo1Do//从底部往上扫描//
begin
IfR[J+1]begin
Temp:
=R[J+1];R[J+1]:
=R[J];R[J]:
=Temp;
NoSwap:
=False
end;
end;
IfNoSwapThenReturn//本趟排序中未发生交换，则终止算法//
end
End;//BubbleSort//
该算法的时间复杂性为O（n^2），算法为稳定的排序方
冒泡排序代码
AAuto
bubble_sort=function（array）{
vartemp;
for（i=1;#array）{
//i前面的已经是最小的数，并排序好了
for（j=#array;i+1;-1）{
//挨个比较
if（array[j]//小的总是往前排
bubble=array[j]
array[j]=array[j-1];
array[j-1]=bubble;
}
}
}
}
io.print（“—————-”）
io.print（“冒泡排序（交换类换排序）”）
io.print（“—————-”）
array={2;46;5;17;1;2;3;99;12;56;66;21};
bubble_sort（array,1,#array）
//输出结果
for（i=1;#array;1）{
io.print（array[i]）
}
C语言
基础结构
*/
voidbubble_sort（int*x,intn）
{
intj,k,h,t;
for（h=n-1,h=k;h>0;h–）/*循环到没有比较范围*/
{
for（j=0,k=0;j{
if（*（x+j）>*（x+j+1））/*大的放在后面，小的放到前面*/
{
t=*（x+j）;
*（x+j）=*（x+j+1）;
*（x+j+1）=t;/*完成交换*/
k=j;/*保存最后下沉的位置。
这样k后面的都是排序排好了的。
*/
}
}
}
}
程序1：
voidbubble_sort（intarray[],intn）
{
inti,j,flag,temp;
for（i=0;i{
flag=1;
for（j=0;j{
if（array[j]>array[j+1]）
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=0;
}
}
if（1==flag）
printf（“%d“,i）;//首先打印出，在第几层循环时顺序已排好
break;//跳出循环
}
return;
}
程序2：
#include
main（）
{
longa,x,k,i[100],s;
charch;
for（a=0;;a++）
{
printf（“输入一个数，输完一个数按回车，最后一个数末尾要加n:
”）;
scanf（“%ld%c”,&i[a],&ch）;
if（a==99）
{
printf（“注意！
输入的数超过100个”）;
break;
}
elseif（ch==’n'）
break;
}
do{
x=0;
for（k=0;k{
if（i[k]>i[k+1]）
{
s=i[k+1];i[k+1]=i[k];
i[k]=s;x++;
}
}
}while（x!
=0）;
printf（“从小到大排列为：
”）;
for（k=0;kprintf（“%ld<”,i[k]）;
printf（“%ld”,i[a]）;
}
C++
#include
#defineLEN9
usingnamespacestd;
intmain（）
{
intnArray[LEN];
for（inti=0;i{
nArray[i]=LEN-i;//赋初值
}
cout<<”原始数据为：
”<for（intj=0;j{
cout<}
cout<for（intm=LEN-1;m>0;m–）
{
inttemp;
for（intn=0;n{
if（nArray[n]>nArray[n+1]）
{
temp=nArray[n];
nArray[n]=nArray[n+1];
nArray[n+1]=temp;
}
}
}
cout<<”排序结果：
”<for（i=0;i{
cout<}
return0;
}
PHP
代码1：
php
//冒泡排序（一维数组）
functionbubble_sort（$array）
{
$count=count（$array）;
if（$count<=0）returnfalse;
for（$i=0;$i<$count;$i++）
{
for（$j=$count-1;$j>$i;$j–）
{
if（$array[$j]<$array[$j-1]）
{
$tmp=$array[$j];
$array[$j]=$array[$j-1];
$array[$j-1]=$tmp;
}
}
}
return$array;
}
//使用实例
$_array=array（’5′,’8′,’5′,’6′,’9′,’3′,’2′,’4′）;
$_array=bubble_sort（$_array）;
print（$_array）;
>
代码2：
php
//冒泡排序
functionmaopaosort（$arr）
{
for（$i=0;$ifor（$j=0;$jif（$arr[$j]>$arr[$j+1]）
{
//交换赋值，不使用中间变量
$arr[$j]=$arr[$j+1]+$arr[$j];
$arr[$j+1]=$arr[$j]-$arr[$j+1];
$arr[$j]=$arr[$j]-$arr[$j+1];
}
}
}
return$arr;
}//endfunc
//实例
$arr=array（7,3,6,1,5,2,11,4,44,33,22,88,44）;
print_r（maopaosort（$arr））;
//结果输出Array（[0]=>1[1]=>2[2]=>3[3]=>4[4]=>5[5]=>6[6]=>7[7]=>11[8]=>22[9]=>33[10]=>44[11]=>44[12]=>88）
>
Ruby
defbubble（arr）
（arr.length-1）.downto
（1）do|j|
a1=arr.dup
j.timesdo|i|
ifarr>arr[i+1]
arr,arr[i+1]=arr[i+1],arr
end
end
breakifa1==arr
end
arr
end
Java
//冒泡排序
publicclassBubbleSort{
publicstaticvoidsort（Comparable[]data）{
//数组长度
intlen=data.length;
for（inti=0;i//临时变量
Comparabletemp=null;
//交换标志，false表示未交换
booleanisExchanged=false;
for（intj=len–1;j>i;j–）{
//如果data[j]小于data[j-1]，交换
if（data[j].compareTo（data[j-1]）<0）{
temp=data[j];
data[j]=data[j-1];
data[j-1]=temp;
//发生了交换，故将交换标志置为真
isExchanged=true;
}//endif
}//endfor
//本趟排序未发生交换，提前终止算法，提高效率
if（!
isExchanged）{
break;
}//endif
}//endfor
}//endsort
publicstaticvoidmain（String[]args）{
//在JDK1.5版本以上，基本数据类型可以自动装箱
//int,double等基本类型的包装类已实现了Comparable接口
Comparable[]c={4,9,23,1,45,27,5,2};
sort（c）;
for（Comparabledata:
c）{
System.out.println（data）;
}
}
}
//简单示例
publicclassTest_Ordination{
publicstaticvoidmain（Stringargs[]）{
int[]s={23,5,12,59,78,21,100,79,66};
for（intj=1;j<=s.length;j++）{
for（inti=0;iif（s[i]>s[i+1]）{
inttemp;
temp=s[i];
s[i]=s[i+1];
s[i+1]=temp;
}
}
}
for（inti=0;iSystem.out.println（s[i]）;
}
}
}
VisualBasic
PrivateSubForm_Load（）
Dima,cAsVariant
DimiAsInteger,jAsInteger,tempAsInteger,bSwapAsBoolean
a=Array（17,45,12,80,50）
Forj=0ToUBound（a）–1
bSwap=False
Fori=0ToUBound（a）–1
If（a（i）>a（i+1））Then‘若是递减，改为a（i）temp=a（i）
a（i）=a（i+1）
a（i+1）=temp
bSwap=True
EndIf
Next
IfbSwap=FalseThen
ExitFor
EndIf
Next
ForEachcIna
Debug.Printc;
Next
EndSub
Pascal
programbubble_sort;
var
a:
array[1..N]of1..MAX;
temp,i,j:
integer;
begin
randomize;
fori:
=1toNdoa:
=1+random（MAX）;
writeln（‘Arraybeforesorted:
’）;
fori:
=1toNdowrite（a,’‘）;
writeln;
fori:
=N-1downto1do
forj:
=1toido
ifa[j]begin
temp:
=a[j];
a[j]:
=a[j+1];
a[j+1]:
=temp;
end;
writeln（‘Arraysorted:
’）;
fori:
=1toNdowrite（a,’‘）;
writeln;
writeln（‘Endsorted.’）;
readln;
end.
C#
staticvoidMain（string[]args）
{
int[]array={23,45,16,7,42};
intlength=array.Length–1;
boolisExchanged=false;
for（inti=0;i{
isExchanged=false;
for（intj=length;j>i;j–）
{
if（array[j]>array[j-1]）
{
inttemp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
isExchanged=true;
}
}
if（!
isExchanged）//一遍比较过后如果没有进行交换则退出循环
break;
}
foreach（intiinarray）
{
Console.WriteLine（i）;
}
Console.Read（）;
}
Python
#BubbleSortusedpython3.1orpython2.x
defbubble（str）:
tmplist=list（str）
count=len（tmplist）
foriinrange（0,count-1）:
forjinrange（0,count-1）:
iftmplist[j]>tmplist[j+1]:
tmplist[j],tmplist[j+1]=tmplist[j+1],tmplist[j]
returntmplist
#useage:
str=“zbac”
print（bubble（str））#['a','b','c','z']
number=[16,134,15,1]
print（bubble（number））#[1,15,16,134]
JS
function（array）{
vari=0,len=array.length,
j,d;
for（;ifor（j=0;jif（array[i]d=array[j];
array[j]=array[i];
array[i]=d;
}
}
}
returnarray;
}
ActionScript
vararr:
Array=newArray（88,0,4,22,89,0,8,15）;
vartemp:
int=0;
for（vari:
int=0;ifor（varj:
int=0;jif（arr[j]>arr[j+1]）{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for（vart:
int=0;ttrace（arr[t]）;
}
伪代码
BUBBLESORT（A）
fori<-1tolength[A]
doforj<-length[A]downtoi+1
doifA[j]thenexchangeA[j]<->A[j-1]
PL/SQL代码
declare
typevarr_typeisvarray（10）ofinteger;
varrvarr_type:
=varr_type（65,32,44,78,20,13,28,99,0,1）;
iinteger;
jinteger;
tinteger;
begin
foriinreverse1..10loop–保证最大的那个值在最终的位置上
forjin1..i-1loop
ifvarr（j）>varr（j+1）then
t:
=varr（j）;
varr（j）:
=varr（j+1）;
varr（j+1）:
=t;
endif;
endloop;
endloop;
foriin1..10loop
dbms_output.put_line（varr（i））;
endloop;
end;
REALBasic
PrivateSubForm_Load（）
Dima,cAsVariant
DimiAsInteger,jAsInteger,tempAsInteger
a=Array（17,45,12,80,50）
Forj=0ToUBound（a）–1
Fori=0ToUBound（a）–1
If（a（j）>a（i））Then
temp=a（j）
a（j）=a（i）
a（i）=temp
EndIf
Next
Next
Fori=0toUBound（a）
msgboxstr（a（i））
Next
EndSub
变种算法
一个叫做鸡尾酒排序（也称双向冒泡排序）的算法，和冒泡排序的“编程复杂度”一样，但对随机序列排序性能稍高于普通冒泡排序，但是因为是双向冒泡，每次循环都双向检查，极端环境下会出现额外的比较，导致算法性能的退化，比如“4、5、7、1、2、3”这个序列就会出现退化
本文信息:
冒泡排序算法及各种程序示例.
升级会员 