轉載自：https://blog.csdn.net/sdddlll/article/details/100574229
之前寫過一篇選擇排序，很多人把它和冒泡排序搞混了，這篇文章對冒泡排序進行一個分析，希望你能分清楚，也希望能在面試的時候能夠完美的回答出冒泡排序，今年的作業據說是不好找，當然運氣占很大一部分，但是實力越強運氣的成分就會相應降低吧，
一、認識冒泡排序
之前在學習排序演算法的時候，冒泡排序往往都是第一個被介紹，就是因為其太簡單，冒泡排序很簡單：
依次比較相鄰的兩個數，將小數放在前面，大數放在后面，
注意：冒泡排序比較的是相鄰的兩個數，而選擇排序比較的整個佇列中最大或者是最小的數進行交換，
第一趟：首先比較第1個和第2個數，將小數放前，大數放后，然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續，直至比較最后兩個數，將小數放前，大數放后，（此時最后一個數一定是整個陣列中的最大值）
第二趟：和第一趟一樣，不過最后一個數已經是最大值，比較到倒數第二個即可，（此時倒數第二個數一定是整個陣列倒數第二大的數）
第三趟、第四趟以此類推即可，
我們來一張動圖演示一下：
上面的這張圖，你多看幾遍就理解了，每次排好都能選出來一哥當前陣列的最大值，OK，如果你理解了之后，下面我們就開始寫代碼來實作一波，
二、代碼實作
1、基本實作
我們先來看一下基本的實作，
public void BubbleSort(int arr[],int n){
int temp;
//有N個數，所以要跑N趟
for(int i = 0;i<n;++i)
//每一趟比較從右往左，得到的是最小值
//每一趟比較從左往右，得到的是最大值
for(int j = n-1;j>i;--j)
//如果右邊的數《左邊的，那就交換位置
if(arr[j]<arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}上面的這種寫法非常簡單，不過我們可能會發現，每一趟其實得到是一個值，這個值可能是當前陣列的最大值又或者是最小值，
這樣做的缺點：
陣列有一部分是本來就有序的，每一趟冒泡那么將會在此部分浪費時間
2、改進
現在我們進行改進：如果我們換一種想法，每一趟掃描的時候，對那些有序的部分，設定一個標志，如果為true表示發生了交換，如果為false，則沒有發生交換，那么我們就可以直接跳過去了，
public static void bubbleSort2(int [] a, int n){
int j, k = n;
//發生了交換就為true, 沒發生就為false
boolean flag = true;
while (flag){
flag=false;//每次開始排序前，都設定flag為未排序過
for(j=1; j<k; j++){
//前面的數字大于后面的數字就交換
if(a[j-1] > a[j]){
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j]=temp;
//表示交換過資料;
flag = true;
}
}
k--;
}
}3、繼續改進
上面的這個雖然很好，必過還是有一定的局限性，比如說陣列的資料量很大有10000個，前面3000個雜亂無章，后面7000個都是排好的，而且還都比前3000個要大，這時候只需要比較前3000個即可，但是上面的改進演算法，在對前3000個進行排序的時候，每次還都要和后7000個比較，這就顯得臃腫了，于是我們進行改進，
public static void bubbleSort3(int [] a, int n){
int j , k;
int flag = n ;
while (flag > 0){
k = flag; //k 來記錄遍歷的尾邊界
flag = 0;
for(j=1; j<k; j++){
if(a[j-1] > a[j]){
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j]=temp;
//表示交換過資料;
flag = j;
}
}
}
}
這個改進就是把flag變為具體的位置了，這樣我們就可以記錄末尾的邊界，這個邊界是排序與不排序的邊界，
三、總結
冒泡排序在筆試或者是面試的時候，涉及到的時間復雜度和空間復雜度都是第一種普通情況，因此它的時間復雜度是O(n^2)，雖然簡單，但是時間上確實是比較長，
我們一定要注意和選擇排序的區別，選擇排序是走一趟找出來一個最小的值和第一個同學交換位置，而冒泡排序是相鄰同學比較高低，這樣走一趟，最高個就沉到末尾了，
間復雜度是O(n^2)，雖然簡單，但是時間上確實是比較長，
我們一定要注意和選擇排序的區別，選擇排序是走一趟找出來一個最小的值和第一個同學交換位置，而冒泡排序是相鄰同學比較高低，這樣走一趟，最高個就沉到末尾了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243120.html
標籤：Java
上一篇：JavaSE 基礎大綱