冒泡排序的核心是一個(gè)嵌套的兩層循環(huán)蟀给，每進(jìn)行一次外層循環(huán)黎做，就把尚未排序的數(shù)中的最大值（降序排序）或者最小值（升序排序）移到外層循環(huán)當(dāng)前索引所在的位置叉跛。因?yàn)檫@個(gè)過程像是氣泡一樣上升，因此得名冒泡排序蒸殿。
使用冒泡排序?qū)?5筷厘、6、2宏所、0酥艳、5 這五個(gè)數(shù)（count = 5）進(jìn)行升序排序，因?yàn)槊看闻判蚨际乔昂髢蓚€(gè)數(shù)進(jìn)行比較爬骤，所以外層循環(huán)需要進(jìn)行 count - 1 = 5 - 1 = 4 次（索引為 0 ~3）充石。內(nèi)層循環(huán)索引 j 從外層循環(huán)當(dāng)前索引位置 i 的下一個(gè)索引 i + 1 開始參與比較，結(jié)束于 count - 1 = 5 - 1 = 4（也就是索引到 4 的位置霞玄，包含索引 4）骤铃。整個(gè)過程如下所示：
| 外層循環(huán)索引 | 內(nèi)層循環(huán)索引 | 當(dāng)前內(nèi)層循環(huán)結(jié)束之后的排序 |
|---|---|---|
| - | - | 5 6 2 0 5 |
| 0 | 1 | 5 6 2 0 5 |
| 0 | 2 | 2 6 5 0 5 |
| 0 | 3 | 0 6 5 2 5 |
| 0 | 4 | 0 6 5 2 5 |
| 1 | 2 | 0 5 6 2 5 |
| 1 | 3 | 0 2 6 5 5 |
| 1 | 4 | 0 2 6 5 5 |
| 2 | 3 | 0 2 5 6 5 |
| 2 | 4 | 0 2 5 6 5 |
| 3 | 4 | 0 2 5 5 6 |
代碼實(shí)現(xiàn)如下：
- 冒泡排序
public class BubbleSort {
public static void main(String[] args) {
int[] data = new int[] {5, 6, 2, 0, 5};
sort(data);
for (int i = 0, size = data.length; i < size; i++) {
System.out.println(data[i]);
}
}
public static void sort(int[] data) {
for (int i = 0, iCount = data.length - 1; i < iCount; i++) {
for (int j = i + 1, jCount = data.length; j < jCount; j++) {
if (data[i] > data[j]) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
}
}
運(yùn)行結(jié)果：
0
2
5
5
6
冒泡排序的時(shí)間復(fù)雜度為 O((N - 1) + (N - 2) + ... + 1) = O((N * (N - 1)) / 2) = O(N^2)拉岁。
