冒泡排序
冒泡排序（Java）
聲明：本文參考http://www.rzrgm.cn/kalton/p/13649798.html
一、原理
- 比較兩個相鄰的元素，將值大的元素交換到右邊
- 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
二、優化原理
如果在某次單趟排序中沒有發生元素的交換，可以說明整個待排序列已經有序
三、時間復雜度
時間復雜度為O(n^2)
四、代碼實現(基本代碼)
1 //冒泡排序 2 public class bubbleSort { 3 public static int[] sort(int arr[]) { 4 System.out.println("------冒泡排序------"); 5 int tmp = 0; 6 for (int i = 0; i < arr.length-1; i++) { 7 for (int j = arr.length-1; j > i; j--) { 8 if (arr[j] < arr[j-1]) { 9 //進行交換 10 tmp = arr[j]; 11 arr[j] = arr[j-1]; 12 arr[j-1] = tmp; 13 } 14 } 15 } 16 return arr; 17 } 18 }
五、優化代碼(一)
public static void bubbleSort(int[] arr){ if (arr == null || arr.length == 0) return;//無序數列的邊界，每次比較只需要比到這里為止 int sortBorder = arr.length-1; for (int i = 0; i < arr.length - 1; i++) { //是否已經有序的標記，默認有序 boolean isSorted = true; for (int j = 0; j < sortBorder; j++) { int tmp = 0; //升序排序>,降序排序< if (arr[j] > arr[j + 1]){ tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; //發生元素交換，序列仍是無序狀態 isSorted = false; } }
//如果沒有發生交換，則待排序列已有序，退出一重循環 if (isSorted){ break; } } }
六、優化代碼(二)：雞尾酒排序
優點：能夠在特定條件下，減少排序的回合數
缺點：代碼量幾乎增加了1倍
應用場景：無序數列中大部分元素已經有序
public static void cockTailSort(int[] arr){ if (arr == null || arr.length == 0) return; // 記錄右側最后一次交換的位置 int lastRightExchangeIndex = 0; // 記錄左側最后一次交換的位置 int lastLeftExchangeIndex = 0; // 無序數列的右邊界，每次比較只需要比到這里為止 int rightSortBorder = arr.length - 1; // 無序數列的左邊界，每次比較只需要比到這里為止 int leftSortBorder = 0; //i設置為1，代表從第1輪開始 for (int i = 1; i < arr.length; i++) { boolean isSorted = true; //奇數，從左到右 if (i % 2 != 0) { for (int j = leftSortBorder; j < rightSortBorder; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; //發生元素交換，序列仍是無序狀態 isSorted = false; //更新為右側最后一次交換元素的位置 lastRightExchangeIndex = j; } } } else { //偶數，從右到左 for (int j = rightSortBorder; j > leftSortBorder; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; //發生元素交換，序列仍是無序狀態 isSorted = false; //更新為左側最后一次交換元素的位置 lastLeftExchangeIndex = j; } } } //更新無序數列的左邊界 leftSortBorder = lastLeftExchangeIndex; //更新無序數列的右邊界 rightSortBorder = lastRightExchangeIndex; if (isSorted) { break; } } }
浙公網安備 33010602011771號