最近在招聘過程中，發(fā)現(xiàn)好多小伙伴最基礎(chǔ)的一些算法回答，接下來會做一個系列，把基礎(chǔ)的排序等算法采用動畫的形式做解析。
這是第一篇「冒泡排序」。
冒泡排序思想
冒泡排序(Bubble Sort)是一種交換排序，基本思想是「兩兩比較相鄰記錄，如果逆序則進行交換，直到?jīng)]有逆序的記錄為止」。
冒泡算法有很多種實現(xiàn)方式，我們在這里只列舉出來兩種實現(xiàn)方式來講解冒泡排序。
排序原理
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
- 對所有的元素重復(fù)以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
排序動畫
「冒泡排序示意動畫」
排序?qū)崿F(xiàn)
「簡單的冒泡排序」
public static void sort(int[] arg) {
//冒泡排序
for (int i = 0; i < arg.length - 1; i++) {
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數(shù)字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
}
}
}
}
上面的代碼是根據(jù)動畫進行的實現(xiàn)，假設(shè)我們的數(shù)據(jù)為{7,5,1,3,2,6}，當(dāng)i=0時，進行第一輪排序，變量j由5開始一直循環(huán)到1，逐個進行兩兩相鄰數(shù)字的比較，最后將數(shù)字最小的1排到第一位，當(dāng)i=1時，進行第二輪排序，變量j由5開始一直循環(huán)到2，逐個進行兩兩相鄰數(shù)字的比較，最后將數(shù)字2排到第二位，依次進行i的下一輪比較，最終實現(xiàn)了數(shù)據(jù)的排序。
在這個過程中，由于數(shù)字像是浮起來的泡泡，所以稱之為冒泡排序。
排序優(yōu)化
上面的算法還有優(yōu)化的空間嗎？我們來看下面的這組數(shù)據(jù)，比如{6,5,4,3,1,2}，經(jīng)過一輪排序已經(jīng)變?yōu)榱藍(lán)6,5,4,3,2,1}，第二輪開始排序之后，還是{6,5,4,3,2,1}，數(shù)字的順序是沒有改變的，說明數(shù)字已經(jīng)處于排序的狀態(tài)了，則沒有必要進行排序，所以還可以進行優(yōu)化，代碼如下：
public void sort(int[] arg) {
//冒泡排序優(yōu)化
for (int i = 0; i < arg.length - 1; i++) {
boolean isSorted = true;
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數(shù)字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
isSorted = false;//如果有數(shù)據(jù)交換，則isSorted為false
}
}
if (isSorted) {//isSorted為true，說明沒有進行數(shù)據(jù)交換，數(shù)據(jù)已經(jīng)有序，則退出循環(huán)
break;
}
}
}
這樣經(jīng)過上面的優(yōu)化，冒泡排序會避免在數(shù)據(jù)已經(jīng)有序的情況下繼續(xù)進行數(shù)據(jù)循環(huán)比較，性能得到了一定的提升。
冒泡排序的復(fù)雜度分析
數(shù)據(jù)正序的情況
比如數(shù)據(jù)為{6,5,4,3,2,1}，按照優(yōu)化后的算法，只需要，只會進行5次比較，也就是n-1次的比較，所以時間復(fù)雜度為O{n}
數(shù)據(jù)逆序的情況
最壞的情況就是全部數(shù)據(jù)都是逆序，比如{6,5,4,3,2,1}，(n(n-1))/2次的數(shù)據(jù)操作和數(shù)據(jù)移動，所以總的時間復(fù)雜度為 (O(n2))
「綜合上面的情況，冒泡排序的時間復(fù)雜度為(O(n2))」
