引入
- 冒泡排序顧名思義，就是像冒泡一樣，泡泡在水里慢慢升上來，由小變大，
- 雖然冒泡排序和冒泡并不完全一樣，但卻可以幫助我們理解冒泡排序，
思路
- 一組無序的陣列，要求我們從小到大排列
- 我們可以先將最大的元素放在陣列末尾
- 再將第二大的數放在陣列的倒數第二個位置
- 再將第三大的數放在陣列的倒數第三個位置
- 以此類推
- 那么現在問題的關鍵就是如何將 第 n 大的數 放在 倒數第 n 個位置 ---> 交換
- 下面是冒泡排序的gif影片，該圖來自于菜鳥教程
實作
提醒
- 現在我們假設無序陣列長度為 n 即下標 [ 0 , n-1 ]
- 當前元素下標為 i ，下一個元素的下標為 j
第一次遍歷 [ 0 , n - 1- 1 ] ---> [ 0 , n -2 ]
- 如果 當前元素 > 后一個元素 ，那么就交換兩個元素 ， 再進行下次遍歷
- 如果 當前元素 > 后一個元素 , 直接進行下次遍歷
- 直到遍歷完成之后，最大的值就在一次一次的交換中被交換到了陣列末尾
- 思考：為什么是從 0 開始遍歷 ，n-2 結束 ?
- 因為 j 為 i 的下一個元素下標 ，如果為 [ 0，n-1 ]的話 ，那么當前元素下標就可以為 n - 1，那么下一個元素的下標就為 n ，顯然陣列下標越界了
- 而且正因為是從 [ 0 , n -2] 范圍遍歷 ，剛好可以保證經過這一輪遍歷后 ，最大的數在陣列末尾 ( i = n - 2 【即為倒數第二個數】 ，j = i + 1【末尾數】)
第二次遍歷 [ 0 , n - 1- 2]----> [ 0 , n -3 ]
- 經過第一次遍歷，我們已經將最大的數移動到了陣列末尾，所以，我們不用在去對末尾以確定的數進行比較，我們可以減少次數，來提高效率
- 再次參考第一次遍歷的步驟
......
最后一次遍歷 [ 0 , n - 1 - (n-1) ] ---- > [ 0 , 0 ]
- 最后一次遍歷的情況就是還剩下兩個元素未進行排序的情況 ，即下標 0 和 下標 1 未進行排序
- 只需對這兩個元素進行排序后，就完成了這個陣列的排序
怎么確定一共需要遍歷幾次及每次遍歷的陣列下標范圍
- 遍歷次數問題
- 我們先來做一個假設
- 如果一個陣列只有兩個元素，那么應該遍歷幾次 ? 1 次
- 如果一個陣列只有三個元素，那么應該遍歷幾次 ? 2次
- 第一次將最大的數放在最末尾 ，第二次將第二大的數放在倒數第二 ， 第三大的元素自然而然就在倒數第三了【即第一個】 ，不用遍歷
- 如果一個陣列只有四個元素，那么應該遍歷幾次 ? 3 次
- 第一次將最大的數放在最末尾 ，第二次將第二大的數放在倒數第二 ， 第三次將第三大的元素放在在倒數第三 ，剩下一個元素，不用排
- 顯而易見，如果有 n 個 元素 ，那么就需要遍歷 n - 1 次
- 每次遍歷陣列下標
- 按照上面的實作部分
- 第一次遍歷我們需要陣列的下標為 [ 0 , n -2 ]
- 第二次遍歷我們需要陣列的下標為 [ 0 , n -3 ]
- 第三次遍歷我們需要陣列的下標為 [ 0 , n -4 ]
- 那么就有一個規律了 ，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) ]
代碼實作
// 冒泡排序演算法
public static int[] bubble(int[] ints){
// 注意我這里使用的是 < ， 而不是我思路中的 <= , 可以自行更改 ，如果沒想明白說明你還沒有理解
// 用 i 來表示一共需要遍歷多少次
for (int i = 0; i < ints.length-1; i++) {
// 真正開始進行遍歷 ，根據 i 的值 不同 ，j 就不同 ，也就是說每次大遍歷中小遍歷的次數不同
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;
}
// 繼續下次遍歷
}
}
return ints;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551195.html
標籤：其他
上一篇：一些常見的字串匹配演算法
下一篇：返回列表