氣泡法（bubble method）是指用氣泡作為變形標誌體，人為加入模型材料內部，以有限應變分析為基礎的一種定量構造模擬方法。將由明膠、甘油和水按比例配製的明膠液倒入按模型幾何形狀、尺寸設計的載入裝置中，並攪動使之形成氣泡；當處於黏彈性狀態、氣泡已不能流動後載入；然後放大拍照、測量與計算，可得出整個模型的有限應變狀態。因便於觀測整個模型內部變形，標誌體反應靈敏，能夠達到較精確要求，故具有廣泛套用前景。
基本介紹
- 中文名：氣泡法
- 外文名：BubbleSort
- 基本概念：依次比較相鄰的兩個數
- 性質：一種定量構造模擬方法
基本概念,產生,排序過程,算法示例,冒泡排序代碼,C,C++,PHP,Ruby,Java,Visual Basic,Pascal,C#,Python,JS,氣泡排序法的改進,性能分析,
基本概念
氣泡排序（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，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反覆進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
算法示例
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),算法為穩定的排序方
冒泡排序代碼
C
1 #include <stdio.h>
2
3 void bubblesort(int v[], int n);
4
5 void bubblesort(int v[], int n){
6 int i, j, t;
7 for(i = 0;i < n;i++){
8 j = n - i - 1;
9 while(j--){
10 if(v[j] < v[j-1]){
11 t = v[j-1];
12 v[j-1] = v[j];
13 v[j] = t;
14 }
15 }
16 }
17 }
18
19 int main(){
20 int arr[] = {1,3,5,2,4,7,6,8,9}, len = 9;
21
22 bubblesort(arr, len);
23
24 while(len--){
25 printf("%d - %d\n", len, arr[len]);
26 }
27
28 return 0;
29 }
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 i=0;i<LEN;i++)cout<<nArray[i]<<" ";
cout<<endl;
//開始冒泡
{
int temp;
for(int i=LEN-1;i>0;i--)
for(int j=0;j<i;j++){
if(nArray[j]>nArray[j+1]){
temp=nArray[j];
nArray[j]=nArray[j+1];
nArray[j+1]=temp;
}
}
}
//結束冒泡
cout<<"排序結果:"<<endl;
for(int i=0;i<LEN;i++)cout<<nArray[i]<<" ";
return 0;
}
PHP
<?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);
?>
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
static void BubbleSort(int a []){
int temp=0;
for (int i = 0; i < a.length ; i++) {
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
Option Explicit
Private Sub Form_click()
Dim a, c As Variant
Dim i As Integer, temp As Integer, w As Integer
a = Array(12, 45, 17, 80, 50)
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
End If
Next
For Each c In a
Print c;
Next
End Sub
Pascal
<i id="bks_9tjbxut2">program bubblesort;
const
N=20;
MAX=10;
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#
public void BubbleSort(int[] array) {
int length = array.Length;
for (int i = 0; i <= length - 2; i++) {
for (int j = length - 1; j >= 1; j--) {
if (array[j] < array[j - 1] ) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
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
<script language="javascript">
var DataOne=new Array(5,6,7,8,3,1,2,-1,100)
var len=DataOne.length
for(var i=0;i<len;i++)
{
for(var j=0;j<len;j++)
{
One=DataOne[j]
Two=DataOne[j+1]
if(One<Two)
{
DataOne[j]=Two
DataOne[j+1]=One
}
}
}
var str=""
for(var n=0;n<len;n++)
{
str+=DataOne[n]+","
}
alert(str)
</script>
氣泡排序法的改進
比如用氣泡排序將4、5、7、1、2、3這6個數排序。在該列中，第二趟排序結束後，數組已排好序，但計算機此時並不知道已經反排好序，計算機還需要進行一趟比較，如果這一趟比較，未發生任何數據交換，則知道已排序好，可以不再進行比較了。因而第三趟比較還需要進行，但第四、五趟比較則是不必要的。為此，我們可以考慮程式的最佳化。
為了標誌在比較中是否進行了，設一個布爾量flag。在進行每趟比較前將flag置成true。如果在比較中發生了數據交換，則將flag置為false，在一趟比較結束後，再判斷flag，如果它仍為true（表明在該趟比較中未發生一次數據交換）則結束排序，否則進行下一趟比較。
