引入
- 冒泡排序顧名思義，就是像冒泡一樣，泡泡在水里慢慢升上來，由小變大。
- 雖然冒泡排序和冒泡并不完全一樣，但卻可以幫助我們理解冒泡排序。
思路
- 一組無序的數(shù)組，要求我們從小到大排列
- 我們可以先將最大的元素放在數(shù)組末尾
- 再將第二大的數(shù)放在數(shù)組的倒數(shù)第二個位置
- 再將第三大的數(shù)放在數(shù)組的倒數(shù)第三個位置
- 以此類推
- 那么現(xiàn)在問題的關鍵就是如何將 第 n 大的數(shù) 放在 倒數(shù)第 n 個位置 ---> 交換
- 下面是冒泡排序的gif動畫，該圖來自于菜鳥教程
實現(xiàn)
提醒
- 現(xiàn)在我們假設無序數(shù)組長度為 n 即下標 [ 0 , n-1 ]
- 當前元素下標為 i ，下一個元素的下標為 j
第一次遍歷 [ 0 , n - 1- 1 ] ---> [ 0 , n -2 ]
- 如果 當前元素 > 后一個元素 ，那么就交換兩個元素 ， 再進行下次遍歷
- 如果 當前元素 > 后一個元素 , 直接進行下次遍歷
- 直到遍歷完成之后，最大的值就在一次一次的交換中被交換到了數(shù)組末尾
- 思考：為什么是從 0 開始遍歷 ，n-2 結束 ?
- 因為 j 為 i 的下一個元素下標 ，如果為 [ 0，n-1 ]的話 ，那么當前元素下標就可以為 n - 1，那么下一個元素的下標就為 n ，顯然數(shù)組下標越界了
- 而且正因為是從 [ 0 , n -2] 范圍遍歷 ，剛好可以保證經過這一輪遍歷后 ，最大的數(shù)在數(shù)組末尾 ( i = n - 2 【即為倒數(shù)第二個數(shù)】 ，j = i + 1【末尾數(shù)】)
第二次遍歷 [ 0 , n - 1- 2]----> [ 0 , n -3 ]
- 經過第一次遍歷，我們已經將最大的數(shù)移動到了數(shù)組末尾，所以，我們不用在去對末尾以確定的數(shù)進行比較，我們可以減少次數(shù)，來提高效率
- 再次引用第一次遍歷的步驟
......
最后一次遍歷 [ 0 , n - 1 - (n-1) ] ---- > [ 0 , 0 ]文章來源：http://www.zghlxwxcb.cn/news/detail-424720.html
- 最后一次遍歷的情況就是還剩下兩個元素未進行排序的情況 ，即下標 0 和 下標 1 未進行排序
- 只需對這兩個元素進行排序后，就完成了這個數(shù)組的排序
怎么確定一共需要遍歷幾次及每次遍歷的數(shù)組下標范圍文章來源地址http://www.zghlxwxcb.cn/news/detail-424720.html
- 遍歷次數(shù)問題
- 我們先來做一個假設
- 如果一個數(shù)組只有兩個元素，那么應該遍歷幾次 ? 1 次
- 如果一個數(shù)組只有三個元素，那么應該遍歷幾次 ? 2次
- 第一次將最大的數(shù)放在最末尾 ，第二次將第二大的數(shù)放在倒數(shù)第二 ， 第三大的元素自然而然就在倒數(shù)第三了【即第一個】 ，不用遍歷
- 如果一個數(shù)組只有四個元素，那么應該遍歷幾次 ? 3 次
- 第一次將最大的數(shù)放在最末尾 ，第二次將第二大的數(shù)放在倒數(shù)第二 ， 第三次將第三大的元素放在在倒數(shù)第三 ，剩下一個元素，不用排
- 顯而易見，如果有 n 個 元素 ，那么就需要遍歷 n - 1 次
- 每次遍歷數(shù)組下標
- 按照上面的實現(xiàn)部分
- 第一次遍歷我們需要數(shù)組的下標為 [ 0 , n -2 ]
- 第二次遍歷我們需要數(shù)組的下標為 [ 0 , n -3 ]
- 第三次遍歷我們需要數(shù)組的下標為 [ 0 , n -4 ]
- 那么就有一個規(guī)律了 ，n - 2 ， n - 3 ， n - 4
- 當我們正在進行第一次遍歷時，用一個變量保存 m = 1 ， 那么第一次遍歷下標可以為 [ 0 , n -1 - m ]
- 當我們正在進行第二次遍歷時，用一個變量保存 m = 2 ， 那么第一次遍歷下標可以為 [ 0 , n -1 - m ]
- 當我們正在進行第三次遍歷時，用一個變量保存 m = 3 ， 那么第一次遍歷下標可以為 [ 0 , n -1 - m ]
- 當我們正在進行最后一次遍歷時，用一個變量保存 m = n - 1， 那么第一次遍歷下標可以為 [ 0 , n -1 - m ] ---> [ 0 , n - 1 - (n -1) ]
代碼實現(xiàn)
// 冒泡排序算法
public static int[] bubble(int[] ints){
// 注意我這里使用的是 < ， 而不是我思路中的 <= , 可以自行更改 ，如果沒想明白說明你還沒有理解
// 用 i 來表示一共需要遍歷多少次
for (int i = 0; i < ints.length-1; i++) {
// 真正開始進行遍歷 ，根據(jù) i 的值 不同 ，j 就不同 ，也就是說每次大遍歷中小遍歷的次數(shù)不同
for (int j = 0; j < ints.length-1-i; j++) {
// 如果前一個元素 > 后一個元素 ，則交換
if (ints[j] > ints[j+1]){
int temp = ints[j];
ints[j] = ints[j+1];
ints[j+1] = temp;
}
// 繼續(xù)下次遍歷
}
}
return ints;
}
到了這里，關于排序算法之詳解冒泡排序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
