朴人博客

冒泡排序（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

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//

Begin

For I := 1 To N-1 Do //做N-1趟排序//

begin

NoSwap := True; //置未排序的标志//

For J := N – 1 DownTo 1 Do //从底部往上扫描//

begin

If R[J+1]< R[J] Then //交换元素//

begin

Temp := R[J+1]; R[J+1] := R[J]; R[J] := Temp;

NoSwap := False

end;

end;

If NoSwap Then Return//本趟排序中未发生交换，则终止算法//

end

End; //BubbleSort//

该算法的时间复杂性为O(n^2），算法为稳定的排序方

冒泡排序代码
AAuto
　　bubble_sort = function(array){

var temp;

for( i=1;#array ){

//i前面的已经是最小的数，并排序好了

for(j=#array;i+1;-1）{

//挨个比较

if(array[j]<array[j-1]){

//小的总是往前排

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语言
基础结构
　　*/

void bubble_sort(int *x,int n)

{

int j,k,h,t;

for (h=n-1,h=k; h>0; h–) /*循环到没有比较范围*/

{

for (j=0,k=0; j<h; j++) /*每次预置k=0，循环扫描后更新k*/

{

if (*(x+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 < n-i-1; 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<STDIO.H>

main()

{

long a,x,k,i[100],s;

char ch;

for(a=0;;a++)

{

printf(“输入一个数，输完一个数按回车，最后一个数末尾要加n:”);

scanf(“%ld%c”,&i[a],&ch);

if(a==99）

{

printf(“注意！输入的数超过100个”);

break;

}

else if(ch==’n’)

break;

}

do{

x=0;

for(k=0;k<a;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;k<a;k++)

printf(“%ld<“,i[k]);

printf(“%ld”,i[a]);

}
C++
　　#include <iostream>

#define LEN 9

using namespace std;

int main()

{

int nArray[LEN];

for(int i=0;i<LEN;i++)

{

nArray[i]=LEN-i; //赋初值

}

cout<<“原始数据为：”<<endl;

for(int j=0;j<LEN;j++)

{

cout<<nArray[j]<<” “;

}

cout<<endl;

for(int m=LEN-1;m>0;m–)

{

int temp;

for(int n=0;n<m;n++)

{

if(nArray[n]>nArray[n+1])

{

temp=nArray[n];

nArray[n]=nArray[n+1];

nArray[n+1]=temp;

}

}

}

cout<<“排序结果：”<<endl;

for(i=0;i<LEN;i++)

{

cout<<nArray[i]<<” “;

}

return 0;

}
PHP
　　代码1：

<?php

//冒泡排序（一维数组）

function bubble_sort($array)

{

$count = count($array);

if ($count <= 0) return false;

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

//冒泡排序

function maopaosort($arr)

{

for ($i=0;$i<count($arr)-1;$i++ ) {

for ($j=0;$j<count($arr)-1-$i;$j++ ) {

if($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;

} // 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 )

>
Ruby
　　def bubble(arr)

(arr.length-1）.downto（1） do |j|

a1 = arr.dup

j.times do |i|

if arr > arr[i+1]

arr,arr[i+1] = arr[i+1],arr

end

end

break if a1 == arr

end

arr

end
Java
　　// 冒泡排序

public class BubbleSort {

public static void sort(Comparable[] data) {

// 数组长度

int len = data.length;

for (int i = 0; i < len – 1; i++) {

// 临时变量

Comparable temp = null;

// 交换标志，false表示未交换

boolean isExchanged = false;

for (int j = 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;

}// end if

}// end for

// 本趟排序未发生交换，提前终止算法，提高效率

if (!isExchanged) {

break;

}// end if

}// end for

}// end sort

public static void main(String[] args) {

// 在JDK1.5版本以上，基本数据类型可以自动装箱

// int,double等基本类型的包装类已实现了Comparable接口

Comparable[] c = { 4,9,23,1,45,27,5,2 };

sort(c);

for (Comparable 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;i<s.length-1;i++){

if(s[i]>s[i+1]){

int temp;

temp = s[i];

s[i] = s[i+1];

s[i+1] = temp;

}

}

}

for(int i=0;i<s.length;i++){

System.out.println(s[i]);

}

}

}
Visual Basic
　　Private Sub Form_Load()

Dim a,c As Variant

Dim i As Integer,j As Integer,temp As Integer,bSwap As Boolean

a = Array（17,45,12,80,50）

For j = 0 To UBound(a) – 1

bSwap = False

For i = 0 To UBound(a) – 1

If (a(i) > a(i + 1）) Then ‘若是递减，改为a(i)<a(i+1）

temp = a(i)

a(i) = a(i + 1）

a(i + 1） = temp

bSwap = True

End If

Next

If bSwap = False Then

Exit For

End If

Next

For Each c In a

Debug.Print c;

Next

End Sub
Pascal
　　program bubble_sort;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln(‘Array before sorted:’);

for i:=1 to N do write(a,’ ‘);

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]<a[j+1] then

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+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 = 0; i < length; i++)

{

isExchanged = false;

for (int j = length; j > i; j–)

{

if (array[j] > array[j – 1])

{

int temp = array[j];

array[j] = array[j – 1];

array[j – 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.x

def bubble(str):

tmplist = list(str)

count = len(tmplist)

for i in range(0,count-1）:

for j in range(0,count-1）:

if tmplist[j] > tmplist[j+1]:

tmplist[j],tmplist[j+1] = tmplist[j+1],tmplist[j]

return tmplist

#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){

var i = 0,len = array.length,

j,d;

for(; i<len; i++){

for(j=0; j<len; j++){

if(array[i] < array[j]){

d = array[j];

array[j] = array[i];

array[i] = d;

}

}

}

return array;

}
Action Script
　　var arr:Array=new Array（88,0,4,22,89,0,8,15）;

var temp:int=0;

for(var i:int=0;i<arr.length;i++){

for(var j:int=0;j<arr.length-i;j++){

if(arr[j]>arr[j+1]){

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

for(var t:int=0;t<arr.length;t++){

trace(arr[t]);

}
伪代码
　　BUBBLESORT(A)

for i <- 1 to length[A]

do for j <- length[A] downto i + 1

do if A[j]<A[j – 1]

then exchange A[j] <-> A[j-1]

PL/SQL代码　

declare

type 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;

begin

for i in reverse 1..10 loop –保证最大的那个值在最终的位置上

for j in 1..i-1 loop

if varr(j)>varr(j+1） then

t:=varr(j);

varr(j):=varr(j+1）;

varr(j+1）:=t;

end if;

end loop;

end loop;

for i in 1..10 loop

dbms_output.put_line(varr(i));

end loop;

end;
REAL Basic
　　Private Sub Form_Load()

Dim a,c As Variant

Dim i As Integer,j As Integer,temp As Integer

a = Array（17,45,12,80,50）

For j = 0 To UBound(a) – 1

For i = 0 To UBound(a) – 1

If (a(j) > a(i)) Then

temp = a(j)

a(j) = a(i）

a(i) = temp

End If

Next

Next

For i=0 to UBound(a)

msgbox str(a(i））
Next
End Sub
变种算法
一个叫做鸡尾酒排序（也称双向冒泡排序）的算法，和冒泡排序的“编程复杂度”一样，但对随机序列排序性能稍高于普通冒泡排序，但是因为是双向冒泡，每次循环都双向检查，极端环境下会出现额外的比较，导致算法性能的退化，比如“4、5、7、1、2、3”这个序列就会出现退化

上一篇: Java中递归函数的使用及递归程序的缺点 下一篇: 简析JAVA中int、String间类型转换