1、基本思想
冒泡排序顧名思義就是整個(gè)過(guò)程像氣泡一樣往上升，單向冒泡排序的基本思想是（假設(shè)由小到大排序）：對(duì)于給定n個(gè)記錄，從第一個(gè)記錄開始依次對(duì)相鄰的兩個(gè)記錄進(jìn)行比較，當(dāng)前面的記錄大于后面的記錄時(shí)，交換位置，進(jìn)行一輪比較和換位后，n個(gè)記錄的最大記錄將位于第n位，然后對(duì)前（n-1）個(gè)記錄進(jìn)行第二輪比較；重復(fù)該過(guò)程，直到記錄剩下一個(gè)為止。
2、復(fù)雜度分析
當(dāng)最好的情況，也就是要排序的序列本身就是有序的，需要進(jìn)行（n-1）次比較，沒(méi)有數(shù)據(jù)交換，時(shí)間復(fù)雜度為O(n).
當(dāng)最壞的情況，即待排序的表是逆序的情況，此時(shí)需要比較次數(shù)為：1+2+3+…+(n-1)=n(n-1)/2次，并作等數(shù)量級(jí)的記錄移動(dòng)，因此總的時(shí)間復(fù)雜度為O(n^2)。
無(wú)論在何種情況下，冒泡排序空間復(fù)雜度（額外空間）總是O(1)。
3、排序過(guò)程如下
以數(shù)組{49,38,65,97,76,13,27,49}為例
從小到大：
從大到小：49,38,65,97,76,13,27,49
4? java代碼實(shí)現(xiàn)
public static void bubbleSort(int[] arr)
{
for(int i=0; i < arr.length-1;i++){
for(int j=0; j < arr.length-i-1;j++)
{?
if(arr[j] > arr[j+1])
{
inttemp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
location = j;
}
}
}
代碼優(yōu)化
1 當(dāng)某一趟遍歷沒(méi)有交換，就說(shuō)明已經(jīng)遍歷好了，就不用再迭代了
public static void sort(int[] arr)
{
int flag;// 標(biāo)記
for(int i=0; i < arr.length-1;i++){
flag =1;// 每一次迭代標(biāo)記為1
for(int j=0; j < arr.length-i-1;j++)
{
if(arr[j] > arr[j+1])
{
inttemp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag =0;// 如果有次序交換，標(biāo)記為0
}
}
if(flag ==1)// 沒(méi)有次序交換，排序完成
break;
}
2 記錄每次遍歷數(shù)據(jù)之后交換次序的位置，顯然這個(gè)位置之后的數(shù)據(jù)已經(jīng)有序了不用再排序了。因此通過(guò)記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了。
public static void sort(int[] arr)
{
intlocation;// 標(biāo)記
intn = arr.length -1;// 初始化最后交換位置為最后一個(gè)元素
for(int i=0; i < arr.length-1;i++){
{
location = n;// 記錄最后發(fā)生交換的位置
for(int j=0; j < arr.length-i-1;j++)
{
if(arr[j] > arr[j+1])
{
inttemp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
n = j;// 記錄無(wú)序位置的結(jié)束 ，有序從j+1位置開始
}
}
if(n == location)// 沒(méi)有次序交換，排序完成
break;
}
}
實(shí)際上，由于在大量數(shù)據(jù)的情況下幾乎不使用冒泡排序，而使用小數(shù)據(jù)的時(shí)候增加的布爾變量反而會(huì)造成額外的開銷。所以個(gè)人認(rèn)為上面改進(jìn)后的算法只是純理論的，通常，冒泡排序就寫前面一種就行了。
算法穩(wěn)定性
容易看出，在相鄰元素相等時(shí)，我們并不需要交換它們的位置，所以，冒泡排序是穩(wěn)定排序。
算法適用場(chǎng)景
冒泡排序思路簡(jiǎn)單，代碼也簡(jiǎn)單，特別適合小數(shù)據(jù)的排序。但是，由于算法復(fù)雜度較高，在數(shù)據(jù)量大的時(shí)候不適合使用。如果一定要在較多數(shù)據(jù)的時(shí)候使用，最好對(duì)算法加以改進(jìn)，例如選擇排序法。
