冒泡排序法的原理是，每次比較相鄰的兩個元素，如果它們的順序錯誤就把它們交換過來。

例如對4 3 6 2 7 1 5這7個數字進行從小到大的排序，從最左側開始，首先比較4和3

因為是從小到大排序，4和3的順序顯然是錯誤的，交換他們，得到

接下來比較4和6

順序是正確的，不需要任何操作。接下來進行下一步，比較6和2

6顯然應該排在2的后面，怎么辦？交換它們，得到

經過前面幾步，已經可以總結出規律，那么接下來要做的比較依次是：

7 > 1? 得到 3 4 2 6 1 7 5

7 > 5? 得到

到此，7的右邊已經沒有數可以比較，第一輪排隊結束。經過這一輪，已經成功的把最大的數，即7放在了最后。但是前面6個數的順序還是不對，但是按照上面的思路很容易想到，對前面6個數再來一遍，即可把6放到倒數第二的位置。然后再對前面5個數重復逐個比較的步驟。。。

7個數字需要進行7-1=6次排隊，每完成一輪排隊，下一輪排隊需要比較的數字個數減1，來看代碼

public?class?BubbleSort?{

public?void?sort(int...?numbers)?{

//n個數執行n-1輪

//每一輪后完成一個數字歸位,?下一輪要比較的數字個數減1(所以內層循環是j?

int?n?=?numbers.length?-?1;

int?t;

for(int?i?=?0;?i?

for(int?j?=?0;?j?

if(numbers[j]?>?numbers[j?+?1])?{

t?=?numbers[j];

numbers[j]?=?numbers[j?+?1];

numbers[j?+?1]?=?t;

}

}

}

}

}

測試

public?static?void?main(String[]?args)?{

int[]?numbers?=?new?int[]{?4,?3,?6,?2,?7,?1,?5?};

System.out.print("before:?");

for(int?i?=?0;?i?

System.out.print(numbers[i]?+?"??");

}

System.out.println();

new?BubbleSort().sort(numbers);

System.out.print("after:?");

for(int?i?=?0;?i?

System.out.print(numbers[i]?+?"??");

}

System.out.println();

}

輸出

before:?4??3??6??2??7??1??5

after:?1??2??3??4??5??6??7

冒泡排序的核心是兩層嵌套的循環，時間復雜度是O(N^2)，即對N個數排序，需要近似執行N的平方次。因為效率較低，實際開發中基本不會使用，但是因為簡單易懂通常做為學習算法的入門案例。

如果用上面的代碼對1 2 3 4 5 6 7做從小到大排列，會發現雖然數字已經排列好，但是程序還是要忠實的執行完全部兩層循環。對這種情況，我們可以引入一個變量來記錄一次內層循環中交換數字的個數，如果交換個數為0，則提前終止循環，在某些情況下可以提高效率。

public?void?betterSort(boolean?descend,?int...?numbers)?{

System.out.print("before:?");

for(int?i?=?0;?i?

System.out.print(numbers[i]?+?"??");

}

System.out.println();

//n個數執行n-1輪

//每一輪后完成一個數字歸位,?下一輪要比較的數字個數減1(所以內層循環是j?

int?n?=?numbers.length?-?1;

int?t;

int?flag?=?0;

for(int?i?=?0;?i?

for(int?j?=?0;?j?

if(descend)?{?//從大到小

if(numbers[j]?

t?=?numbers[j];

numbers[j]?=?numbers[j?+?1];

numbers[j?+?1]?=?t;

flag?=?1;

}

}?else?{

if(numbers[j]?>?numbers[j?+?1])?{

t?=?numbers[j];

numbers[j]?=?numbers[j?+?1];

numbers[j?+?1]?=?t;

flag?=?1;

}

}

}

if(flag?==?0)?{

break;

}?else?{

flag?=?0;

}

}

System.out.print("after:?");

for(int?i?=?0;?i?

System.out.print(numbers[i]?+?"??");

}

System.out.println();

}

增加一個變量需要額外占用內存空間，因此，這個方法是以空間換時間。