波风麒若 我的主页帐号设置退出秀才 二级|消息 私信通知|我的百科我的贡献草稿箱我的任务为我推荐|百度首页 新闻网页贴吧知道音乐图片视频地图百科文库
帮助 首页 自然 文化 地理 历史 生活 社会 艺术 人物 经济 科技 体育 图片 数字博物馆 核心用户 百科商城
冒泡排序
求助编辑百科名片
大泡在上，小泡在下——冒泡排序基本原理。冒泡排序，是指计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数
目录
基本概念产生
排序过程
性能分析
改进
算法示例AAuto
C语言
C++
PHP
Ruby
Java
Visual Basic
Pascal
C#
Python
JS
Action Script
伪代码
REAL Basic
GO语言
变种算法
展开基本概念 产生
排序过程
性能分析
改进
算法示例 AAuto
C语言
C++
PHP
Ruby
Java
Visual Basic
Pascal
C#
Python
JS
Action Script
伪代码
REAL Basic
GO语言
变种算法
展开
编辑本段基本概念冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复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，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。在新一轮排序开始时，检查此标志，若此标志为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]
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 *a, int n)
{
int *p1 = a;
int *p2 = a;
int k;
int j;
for (int i = 0; i < n; i++)
{
p2 = p1;
p2++;
for (j = n - i - 1; j > 0; j--)
{
if (*p2 < *p1) // 升序
{
k = *p1;
*p1 = *p2;
*p2 = k;
}
p2++;
}
p1++;
}
}
程序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：（可进行2个数以上大小比较，程序参考作者：赵杰）
#include
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
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
printf("%ld",i[a]);
return 0;
}
C++
#include
using namespace std;
/*冒泡排序，又叫起泡排序*/
void bubbleSort (int arrays[], int size)
{
bool changed = true;
do
{
changed = false;
for (int i = 0; i < size - 1; i++)//注意：此处循环条件i < size - 1容易写错为i < size
{
if ( arrays[i] > arrays[i + 1] )
{
swap( a
rrays[i], arrays[i + 1]);
changed = true;
}
}
}while (changed);
}
/*测试函数*/
int main ()
{
int num[] = {5,6,9,8,7,2,3,15,26,3,12,-5,-2,16,1,1,9,9};
cout << "初始数据为：";
for (int i = 0; i < 18; i++)
cout << num[i] << " ";
cout << endl;
bubbleSort(num, 18);//使用冒泡排序
cout << "排序之后：";
for (int j = 0; j <18; j++)
cout << num[j] << " ";
cout << endl;
system("pause");
return 0;
}
PHP
代码1：
[1]//冒泡排序（一维数组）
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：
//冒泡排序
function maopaosort($arr)
{
for ($i=0;$i
{
//交换赋值，不使用中间变量
$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 {
static void bubblesort(int[] a) {
int temp;
for (int i = 0; i < a.length-1; i++) {//-1是因为最后一个没必要再跟它本身比较
for (int j = 0; j < a.length-i-1 ; j++) {
if (a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
}
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) = 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]
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 isExcha
nged = 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）[::-1]:
for j in range(0,i）:
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 length = array.length, temp;
for(var i = 0; i < length - 2; i++){
for (var j = length -1; j >=1;j--) {
if (array[j] < array[j - 1]){
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
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
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(var t:int=0;t
}
伪代码
BUBBLESORT(A)
for i <- 1 to length[A]
do for j <- length[A] downto i + 1
do if A[j]
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
GO语言
// find the small one in the arrary
// bubble sort
package main
import "fmt"
func bubblesort ( in []int ) {
change := true
for i := 0; i< len(in) - 1 ; i++ {
change = true
for j := 0 ; j< len(in) - i - 1 ; j++ {
if in[j] > in[j+1] {
in[j],in[j+1] = in[j+1],in[j]
change = false
} //end for if
} //end for j
if change {
break
}
} //end for i
}
func main() {
x := []int{48,96,86,68,
57,82,63,70,
37,34,83,27,
19,97,9,17}
bubblesort(x)
xlen := len(x)
res := x[1]
bigger := x[xlen-1]
fmt.Println("the small one is :",res)
fmt.Println("the bigger one is :",bigger)
}
变种算法
一个叫做鸡尾酒排序（也称双向冒泡排序）的算法，
和冒泡排序的“编程复杂度”一样，但对随机序列排序性能稍高于普通冒泡排序，但是因为是双向冒泡，每次循环都双向检查，极端环境下会出现额外的比较，导致算法性能的退化，比如“4、5、7、1、2、3”这个序列就会出现退化
参考资料
1． php 冒泡排序算法 ．中国Linux联盟 [引用日期2012-11-28] ．
扩展阅读：
1
https://www.doczj.com/doc/2b9974468.html,/idche/archive/2011/02/16/1956397.html //JS版本常见排序算法
2
[1] 黄福员，聂瑞华。 冒泡排序算法的改进 [J]. 微机发展， 2003, 13 (11) _3 .
3
[1 ] 郑国彪，曹侃宇。 冒泡排序法及其改进 [J]. 青海大学学报（自然科学版）, 2002, 20 (3)_5 .
开放分类：
数据结构 编程 算法 应用科学 科学 计算机术语 计算机编程 排序组合
我来完善 “冒泡排序”相关词条：
快速排序算法 基数排序 直接插入排序 堆排序 指针函数 函数指针 希尔排序 结构体 杨辉三角 插入排序 选择排序 归并排序 递归 Shell排序
百度百科中的词条正文与判断内容均由用户提供，不代表百度百科立场。如果您需要解决具体问题（如法律、医学等领域），建议您咨询相关领域专业人士。
本词条对我有帮助添加到搜藏 分享到:更多
合作编辑者
sai129198 ， zyh127 ， 440700383685 ， tpcrack ， 食色瞳孔 ， simingshen ， lee121314 ， t890211 ， jklf407 ， firerun 更多
如果您认为本词条还需进一步完善，百科欢迎您也来参与 编辑词条 在开始编辑前，您还可以先学习如何编辑词条
如想投诉，请到百度百科投诉中心；如想提出意见、建议，请到百度百科吧。
百度百科内容方针
提倡有可靠依据、权威可信的内容鼓励客观、中立、严谨的表达观点不欢迎恶意破坏、自我或商业宣传在这里你可以
编辑
质疑
投诉
全方位的质量监督
学术委员会：为亿万网友提供权威意见质量委员会：把控质量，做更好的知识波风麒若
00
去兑换>>您尚无道具可使用
成长任务日常任务本月累计点亮0天。今日笑脸还没点亮哦。
名符图实：参加任务，拿点亮任务日历获得财富值热词推送编辑热词可获得额外经验值
词条动态进入我的百科您目前的等级是2级
您目前的经验值是154点
您还需346点经验值即可升为3级
词条统计
浏览次数：约 481909次
编辑次数：128次 历史版本
词条讨论：4次 讨论历史
最近更新：2013-01-13
创建者：maxlcl
更多贡献光荣榜
辛勤贡献者：
yangke19941112 版本
440700383685 版本
sai129198 版本
zenghuan4172 版本
zdz1028 版本
查看更多贡献者
最新动态
热气球的前世今生：
百科消息：
百科新版客户端新增图册等功能
北京民俗博物馆加入数字博物
馆
有奖调研：说说你眼中的百科
写游记赢泰国免费名额
漫画家倾力巨献潮人专属手机壁纸
百科全新内容方针提升词条权威
? 2013 Baidu 使用百度前必读 | 百科协议 | 百度百科合作平台
冒泡排序基本概念产生排序过程性能分析改进算法示例AAutoC语言C++PHPRubyJavaVisual BasicPascalC#PythonJSAction Script伪代码REAL BasicGO语言变种算法
参考资料
退出
若有错误，请划词选中错误内容并按提示质疑，为词条的质量提升做出贡献。
展开收起
若您对这些内容有可信的参考资料，并掌握百科编辑技巧，欢迎你直接编辑词条。
如果你想了解更详细的质疑原因，并参与更多的词条讨论，欢迎进入词条讨论页。
参与质疑×