看動(dòng)圖學(xué)算法：冒泡排序算法的原理和Java講解
冒泡算法是一種簡(jiǎn)單的排序算法，它的基本思想是通過相鄰元素之間的比較和交換，將大的元素慢慢地“冒泡”到數(shù)組的最后一個(gè)位置。冒泡算法在實(shí)現(xiàn)上非常簡(jiǎn)單，但它的時(shí)間復(fù)雜度較高，通常僅適用于小型數(shù)據(jù)集的排序。
一、算法原理
冒泡算法的原理非常簡(jiǎn)單：首先將要排序的數(shù)列分成兩部分，已排序的部分和未排序的部分。每一輪排序中，從第一個(gè)元素開始，依次比較相鄰的兩個(gè)元素，如果前一個(gè)元素大于后一個(gè)元素，則交換兩個(gè)元素的位置，直到整個(gè)數(shù)列都排好序?yàn)橹埂?/p>
假設(shè)要排序的數(shù)列為A[]，其長(zhǎng)度為n。則第一輪排序時(shí)需要比較n-1次，第二輪排序時(shí)需要比較n-2次，以此類推，第k輪排序時(shí)需要比較n-k次。因此，總共需要進(jìn)行n(n-1)/2次比較，時(shí)間復(fù)雜度為O(n^2)。
二、算法流程
具體來說，冒泡算法的流程如下：
1、首先，將要排序的數(shù)列A[]作為輸入，其長(zhǎng)度為n；
2、然后，從第一個(gè)元素開始，依次比較相鄰的兩個(gè)元素，如果前一個(gè)元素大于后一個(gè)元素，則交換兩個(gè)元素的位置；
3、接著，將指針向后移動(dòng)一位，繼續(xù)比較相鄰的兩個(gè)元素，并進(jìn)行交換，直到整個(gè)數(shù)列都排好序?yàn)橹梗?/p>
4、最后，輸出已排序的數(shù)列A[]。
三、優(yōu)化算法
冒泡排序的時(shí)間復(fù)雜度為O(n^2)，當(dāng)數(shù)據(jù)量較大時(shí)，會(huì)出現(xiàn)比較耗費(fèi)時(shí)間的情況。因此，我們可以進(jìn)行一些優(yōu)化，使得算法的效率更高。
1、當(dāng)在某一輪排序中，沒有任何一次交換操作發(fā)生時(shí)，表示數(shù)列已經(jīng)有序，此時(shí)可以直接退出循環(huán)。
2、在排序過程中，記錄最后一次發(fā)生交換的位置，之后的數(shù)列都已排好序，因此可以減少比較次數(shù)：
public class BubbleSortAnimation {
public static void main(String[] args) {
int[] arr = {10, 2, 1, 42, 22, 8, 9, 11, 1, 4, 6, 33, 20, 11, 17, 55, 24};
int n = arr.length;
int lastExchange = 0; // 最后一次交換位置
int sortBorder = n - 1; // 無序數(shù)列的邊界
for (int i = 0; i < n - 1; i++) {
boolean flag = true; // 標(biāo)記是否發(fā)生交換
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false; // 發(fā)生交換
lastExchange = j; // 記錄最后一次交換位置
}
}
// 打印每一輪排序后的數(shù)組情況
System.out.print("第 " + (i + 1) + " 輪排序后的數(shù)組為：");
for (int k = 0; k < n; k++) {
System.out.print(arr[k] + " ");
}
System.out.println();
sortBorder = lastExchange; // 更新無序數(shù)列的邊界
if (flag) {
break; // 本輪排序未發(fā)生交換，說明已有序
}
}
}
}示例代碼的輸出日志:
第 1 輪排序后的數(shù)組為：2 1 10 22 8 9 11 1 4 6 33 20 11 17 42 24 55
第 2 輪排序后的數(shù)組為：1 2 10 8 9 11 1 4 6 22 20 11 17 33 24 42 55
第 3 輪排序后的數(shù)組為：1 2 8 9 10 1 4 6 11 20 11 17 22 24 33 42 55
第 4 輪排序后的數(shù)組為：1 2 8 9 1 4 6 10 11 11 17 20 22 24 33 42 55
第 5 輪排序后的數(shù)組為：1 2 8 1 4 6 9 10 11 11 17 20 22 24 33 42 55
第 6 輪排序后的數(shù)組為：1 2 1 4 6 8 9 10 11 11 17 20 22 24 33 42 55
第 7 輪排序后的數(shù)組為：1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55
第 8 輪排序后的數(shù)組為：1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55動(dòng)圖效果:
冒泡排序過程演示，若無法顯示動(dòng)圖請(qǐng)刷新重試
四、算法分析
1、時(shí)間復(fù)雜度：最好情況下為O(n)，即數(shù)列已經(jīng)排序完成，無需進(jìn)行任何比較操作；最壞情況下為O(n^2)；平均情況下為O(n^2)。
2、空間復(fù)雜度：由于只需要一個(gè)額外的變量來保存臨時(shí)變量，并沒有使用任何額外的空間，空間復(fù)雜度為O(1)。
3、穩(wěn)定性：冒泡排序是一種穩(wěn)定排序算法，因?yàn)樵诒容^相鄰的兩個(gè)元素時(shí)，只有在前一個(gè)元素大于后一個(gè)元素時(shí)才會(huì)進(jìn)行交換，不會(huì)改變相同元素之間的順序。
五、總結(jié)
冒泡排序是一種簡(jiǎn)單而又經(jīng)典的排序算法，雖然其時(shí)間復(fù)雜度較高，但由于其實(shí)現(xiàn)簡(jiǎn)單，易于理解，是許多排序算法中最為基礎(chǔ)的一種。在實(shí)際應(yīng)用中，我們可以根據(jù)具體情況對(duì)其進(jìn)行優(yōu)化，從而提高算法的效率。
分享到微信 
分享到微博
