冒泡排序算法及各种程序示例.docx

1、冒泡排序算法及各种程序示例冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复

2、以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和aj+1标识，i的值依次为1,2,9，对于每一个i,j的值依次为1,2,10-i。在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而倍受青睐。设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡

3、，就使其向上”漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。若记录序列的初始状态为”正序”，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为”逆序”，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。冒泡排序法存在的不足及改进方法：第一，在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志单元flag，将其设置为OFF，表示被排序的表示是一个无序的表。在每一排序开始时，检查此标志，若此标志为0，则结束排序；否则进

4、行排序；第二，当排序的数据比较多时排序的时间会明显延长。改进方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完局部冒泡排序算法对冒泡排序的改进：在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描

5、中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。程序示例DELPHI49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 3

6、8 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97Procedure BubbleSort(Var R : FileType) /从下往上扫描的起泡排序/BeginFor I := 1 To N-1 Do /做N-1趟排序/beginNoSwap := True; /置未排序的标志/For J := N 1 DownTo 1 Do /从底部往上扫描/beginIf RJ+1 RJ Then /交换

7、元素/beginTemp := RJ+1; RJ+1 := RJ; RJ := Temp;NoSwap := Falseend;end;If NoSwap Then Return/本趟排序中未发生交换，则终止算法/endEnd; /BubbleSort/该算法的时间复杂性为O(n2），算法为稳定的排序方冒泡排序代码AAutobubble_sort = function(array)var temp;for( i=1;#array )/i前面的已经是最小的数，并排序好了for(j=#array;i+1;-1）/挨个比较if(arrayj0; h) /*循环到没有比较范围*/for (j=0,k=

8、0; j *(x+j+1）) /*大的放在后面，小的放到前面*/t = *(x+j);*(x+j) = *(x+j+1）;*(x+j+1） = t; /*完成交换*/k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/程序1：void bubble_sort(int array,int n)int i,j,flag,temp;for(i = 0; i n-1; i+)flag = 1;for(j = 0; j arrayj+1)temp= arrayj;arrayj = arrayj+1;arrayj+1 = temp;flag = 0;if（1 = flag)printf

9、(“%d “,i); /首先打印出，在第几层循环时顺序已排好break; /跳出循环return;程序2：#includemain()long a,x,k,i100,s;char ch;for(a=0;a+)printf(“输入一个数，输完一个数按回车，最后一个数末尾要加n:”);scanf(“%ld%c”,&ia,&ch);if(a=99）printf(“注意！输入的数超过100个”);break;else if(ch=n)break;dox=0;for(k=0;kik+1)s=ik+1;ik+1=ik;ik=s;x+;while(x!=0);printf(“从小到大排列为：”);for(k

10、=0;ka;k+)printf(“%ld”,ik);printf(“%ld”,ia);C+#include #define LEN 9using namespace std;int main()int nArrayLEN;for(int i=0;iLEN;i+)nArrayi=LEN-i; /赋初值cout”原始数据为：”endl;for(int j=0;jLEN;j+)coutnArrayj” “;cout0;m)int temp;for(int n=0;nnArrayn+1)temp=nArrayn;nArrayn=nArrayn+1;nArrayn+1=temp;cout”排序结果：”e

11、ndl;for(i=0;iLEN;i+)coutnArrayi” “;return 0;PHP代码1：?php/冒泡排序（一维数组）function bubble_sort($array)$count = count($array);if ($count = 0) return false;for($i=0; $i$i; $j)if ($array$j 代码2：?php/冒泡排序function maopaosort($arr)for ($i=0;$icount($arr)-1;$i+ ) for ($j=0;$j$arr$j+1)/交换赋值，不使用中间变量$arr$j=$arr$j+1+$a

12、rr$j;$arr$j+1=$arr$j-$arr$j+1;$arr$j=$arr$j-$arr$j+1;return $arr; / end func/实例$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 )Rubydef bubble(arr)(arr.length-1）.downto（1） do |j|a

13、1 = arr.dupj.times do |i|if arr arri+1arr,arri+1 = arri+1,arrendendbreak if a1 = arrendarrendJava/ 冒泡排序public class BubbleSort public static void sort(Comparable data) / 数组长度int len = data.length;for (int i = 0; i i; j) / 如果dataj小于dataj - 1，交换if (pareTo(dataj - 1) 0) temp = dataj;dataj = dataj - 1;d

14、ataj - 1 = temp;/ 发生了交换，故将交换标志置为真isExchanged = true;/ end if/ end for/ 本趟排序未发生交换，提前终止算法，提高效率if (!isExchanged) break;/ end if/ end for/ end sortpublic static void main(String args) / 在JDK1.5版本以上，基本数据类型可以自动装箱/ int,double等基本类型的包装类已实现了Comparable接口Comparable c = 4,9,23,1,45,27,5,2 ;sort(c);for (Comparabl

15、e data : c) System.out.println(data);/简单示例public class Test_Ordination public static void main(String args)int s = 23,5,12,59,78,21,100,79,66;for(int j=1;j=s.length;j+)for(int i=0;isi+1)int temp;temp = si;si = si+1;si+1 = temp;for(int i=0;i a(i + 1）) Then 若是递减，改为a(i)a(i+1）temp = a(i)a(i) = a(i + 1）a

16、(i + 1） = tempbSwap = TrueEnd IfNextIf bSwap = False ThenExit ForEnd IfNextFor Each c In aDebug.Print c;NextEnd SubPascalprogram bubble_sort;vara:array1.N of 1.MAX;temp,i,j:integer;beginrandomize;for i:=1 to N do a:=1+random(MAX);writeln(Array before sorted:);for i:=1 to N do write(a, );writeln;for

17、i:=N-1 downto 1 dofor j:=1 to i doif ajaj+1 thenbegintemp:=aj;aj:=aj+1;aj+1:=temp;end;writeln(Array sorted:);for i:=1 to N do write(a, );writeln;writeln(End sorted.);readln;end.C#static void Main(string args)int array = 23,45,16,7,42 ;int length = array.Length 1;bool isExchanged = false;for (int i =

18、 0; i i; j)if (arrayj arrayj - 1)int temp = arrayj;arrayj = arrayj - 1;arrayj - 1 = temp;isExchanged = true;if (!isExchanged)/一遍比较过后如果没有进行交换则退出循环break;foreach (int i in array)Console.WriteLine(i);Console.Read();Python#BubbleSort used python3.1 or python 2.xdef bubble(str):tmplist = list(str)count =

19、len(tmplist)for i in range(0,count-1）:for j in range(0,count-1）:if tmplistj tmplistj+1:tmplistj,tmplistj+1 = tmplistj+1,tmplistjreturn tmplist#useage:str = “zbac”print(bubble(str) # a,b,c,znumber=16,134,15,1print(bubble(number) # 1,15,16,134JSfunction(array)var i = 0,len = array.length,j,d;for(; ile

20、n; i+)for(j=0; jlen; j+)if(arrayi arrayj)d = arrayj;arrayj = arrayi;arrayi = d;return array;Action Scriptvar arr:Array=new Array（88,0,4,22,89,0,8,15）;var temp:int=0;for(var i:int=0;iarr.length;i+)for(var j:int=0;jarrj+1)temp=arrj;arrj=arrj+1;arrj+1=temp;for(var t:int=0;tarr.length;t+)trace(arrt);伪代码

21、BUBBLESORT(A)for i - 1 to lengthAdo for j - lengthA downto i + 1do if AjAj - 1then exchange Aj Aj-1PL/SQL代码declaretype varr_type is varray（10） of integer;varr varr_type:=varr_type（65,32,44,78,20,13,28,99,0,1）;i integer;j integer;t integer;beginfor i in reverse 1.10 loop 保证最大的那个值在最终的位置上for j in 1.i-1

22、 loopif varr(j)varr(j+1） thent:=varr(j);varr(j):=varr(j+1）;varr(j+1）:=t;end if;end loop;end loop;for i in 1.10 loopdbms_output.put_line(varr(i);end loop;end;REAL BasicPrivate Sub Form_Load()Dim a,c As VariantDim i As Integer,j As Integer,temp As Integera = Array（17,45,12,80,50）For j = 0 To UBound(a) 1For i = 0 To UBound(a) 1If (a(j) a(i) Thentemp = a(j)a(j) = a(i）a(i) = tempEnd IfNextNextFor i=0 to UBound(a)msgbox str(a(i）NextEnd Sub变种算法一个叫做鸡尾酒排序（也称双向冒泡排序）的算法，和冒泡排序的“编程复杂度”一样，但对随机序列排序性能稍高于普通冒泡排序，但是因为是双向冒泡，每次循环都双向检查，极端环境下会出现额外的比较，导致算法性能的退化，比如“4、5、7、1、2、3”这个序列就会出现退化本文信息:冒泡排序算法及各种程序示例.