算法描述
冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列蘸秘，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來蝗茁。（百度百科）
算法原理
- 兩個(gè)相鄰的元素相比較醋虏，若第一個(gè)比第二個(gè)大，就進(jìn)行交換
- 第二個(gè)和第三個(gè)元素重復(fù)第一步的工作哮翘，直到與最后一個(gè)元素比較完颈嚼，完成后最后一個(gè)元素就是最大的那個(gè)
- 重復(fù)上述兩個(gè)步驟，直到全部元素比較完饭寺。
算法實(shí)現(xiàn)
這里我以Java中的數(shù)組為例阻课，來具體實(shí)現(xiàn)下冒泡排序
假設(shè)數(shù)組為 arr={34,42,78,12,3}，利用冒泡排序法將數(shù)組進(jìn)行排序艰匙。
第一步
- 數(shù)組第一個(gè)數(shù)與第二數(shù)進(jìn)行比較限煞，即 arr[0]=34 與 arr[1]=42 比較，42大于34员凝，所以不交換署驻。數(shù)組為
arr={34,42,78,12,3} - 數(shù)組第二個(gè)數(shù)與第三數(shù)進(jìn)行比較，即 arr[1]=42 與 arr[2]=78 比較，78大于42硕舆，所以不交換秽荞。數(shù)組為
arr={34,42,78,12,3} - 數(shù)組第三個(gè)數(shù)與第四數(shù)進(jìn)行比較，即 arr[2]=78 與 arr[3]=12 比較抚官，78大于12扬跋，所以進(jìn)行交換。數(shù)組為
arr={34,42,12,78,3} - 數(shù)組第四個(gè)數(shù)與第五數(shù)進(jìn)行比較凌节，即 arr[3]=78 與 arr[4]=3 比較钦听，78大于3，所以進(jìn)行交換倍奢。數(shù)組為
arr={34,42,12,3,78}
代碼實(shí)現(xiàn)
for (int x = 0; x < arr.length - 1; x++) {
if (arr[x] > arr[x + 1]) {
int temp = arr[x];
arr[x] = arr[x + 1];
arr[x + 1] = temp;
}
}
注意：代碼實(shí)現(xiàn)時(shí)容易造成數(shù)組越界朴上，所以 for 循環(huán)的判斷條件是 x < arr.length - 1
第二步
重復(fù)第一步工作，但最后不需要與前面比較過的元素在進(jìn)行比較卒煞，所以需要比較的次數(shù)逐漸減少痪宰。
代碼實(shí)現(xiàn)
for (int x = 0; x < arr.length - 2; x++) {
if (arr[x] > arr[x + 1]) {
int temp = arr[x];
arr[x] = arr[x + 1];
arr[x + 1] = temp;
}
}
注意：第二次比較時(shí)，不需要與第一步比較的元素再進(jìn)行比較畔裕，所以 for 循環(huán)的判斷條件是 x < arr.length - 2
重復(fù)上述兩個(gè)步驟衣撬，直到數(shù)組比較完成。
代碼優(yōu)化
由上述實(shí)現(xiàn)代碼發(fā)現(xiàn)扮饶，比較的過程都是相同的具练，只是后一步所需比較的步數(shù)比前一步少一。所以可以用 for 循環(huán)將代碼優(yōu)化甜无，具體代碼如下：
for (int x = 0; x < arr.length; x++) {
for (int y = 0; y < arr.length - 1 - x; y++) {
if (arr[y] > arr[y + 1]) {
int temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
完整代碼請(qǐng)?jiān)L問：https://github.com/xieys 歡迎Follow和star
