冒泡排序法又稱為交換排序法，是由觀察水中冒泡變化構思而成，氣泡隨著水深壓力而改變，氣泡在水底時，壓力最大，氣泡最小；當慢慢浮上水面時，發現氣泡由小漸漸變大，
冒泡排序法的比較方式由第一個元素開始，比較相鄰元素大小，若大小順序有誤，則對調后再進行下一個元素的比較，如此掃描過一次之后就可確保最后一個元素是位于正確的順序，接著再逐步進行第二次掃描，直到完成所有元素的排序關系為止，
演算程序
由此可知 5 個元素的冒泡排序法必須執行 5～1 次掃描，第一次掃描需比較 5～1 次，共比較 4+3+2+1 次
冒泡法分析
- 最壞的情況及平均情況均需比較 (n-1)+(n-2)+(n-3)+...+3+2+1=n(n-1)/2 次；時間復雜度為 O(n^2)，最好的情況只需完成一次掃描，發現沒有做交換的操作則表示已經排序完成，所以只做了 n-1 次比較，時間復雜度為 O(n)，
- 由于冒泡排序為相鄰兩者相互比較對調，并不會更改其原本排序的順序，所以是穩定排序法，
- 只需一個額外的空間，所以空間復雜度為最佳，
- 此排序適用于資料量小或有部分資料已經過排序的情況，
example1
/** * 傳統冒泡排序法 * */ public class BubbleSort { public static void main(String[] args) { int[] data = https://www.cnblogs.com/qpliang/p/{6, 5, 9, 7, 2, 8}; int temp; System.out.print("原始資料為："); for (int i : data) { System.out.print("[" + i + "]"); } System.out.println(); for (int i = data.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) { if (data[j] > data[j + 1]) { temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; } }// 掃描后的結果 System.out.print("第 " + (data.length - i) + " 次結果："); for (int k : data) { System.out.print("[" + k + "]"); } System.out.println(); } System.out.print("排序后結果："); for (int i : data) { System.out.print("[" + i + "]"); } } }
由上面的程式可以看出冒泡排序法有一個缺點，即不管資料是否已排序完成都固定會執行 n(n-1)/2 次，而我們可以通過在程式中加入判斷來判斷何時提前中斷程式，又可得到正確的資料，來提高程式執行效率，
example2
/** * 傳統冒泡排序法 * */ public class BubbleSort { public static void main(String[] args) { int[] data = https://www.cnblogs.com/qpliang/p/{6, 5, 9, 7, 2, 8}; int temp; System.out.print("原始資料為："); for (int i : data) { System.out.print("[" + i + "]"); } System.out.println(); for (int i = data.length - 1; i > 0; i--) { boolean isYes = true; for (int j = 0; j < i; j++) { if (data[j] > data[j + 1]) { temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; isYes = false; } } if (isYes) { break; } // 掃描后的結果 System.out.print("第 " + (data.length - i) + " 次結果："); for (int k : data) { System.out.print("[" + k + "]"); } System.out.println(); } System.out.print("排序后結果："); for (int i : data) { System.out.print("[" + i + "]"); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62069.html
標籤：其他