Java冒泡排序:從小到大的幾種常見寫法,需要具體程式碼範例
冒泡排序是一種簡單的排序演算法,它重複地比較相鄰的兩個元素,並根據大小順序進行交換,直到整個序列有序。在Java中,冒泡排序有幾種常見的寫法和最佳化方式,以下將介紹其中的五種常見寫法並提供具體程式碼實例。
第一種寫法:普通的冒泡排序
普通的冒泡排序直接嵌套兩層循環,外層循環控制比較的輪數,內層循環進行具體的比較和交換。
public static void bubbleSort1(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
第二種寫法:優化外層循環
在第一種寫法的基礎上,如果一輪排序沒有進行任何交換,說明數組已經有序,可以提前結束排序。為了實現這個最佳化,我們可以新增一個標記位元來記錄是否進行了交換。
public static void bubbleSort2(int[] arr) { int n = arr.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = true; } } if (!swapped) { break; } } }
第三種寫法:最佳化內層循環
在第二種寫法的基礎上,可以發現每輪比較都會將最大的元素「冒泡」到最後。因此,每輪比較內層循環的次數可以逐漸減少。
public static void bubbleSort3(int[] arr) { int n = arr.length; int lastSwapIndex; for (int i = 0; i < n - 1; i++) { lastSwapIndex = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } i = n - lastSwapIndex - 2; } }
第四種寫法:優化內外層循環
在第三種寫法的基礎上,如果數組在某輪比較中未發生交換,表示數組後面的元素已經有序,可以提前結束排序。
public static void bubbleSort4(int[] arr) { int n = arr.length; int lastSwapIndex, rightBoundary; rightBoundary = n - 1; for (int i = 0; i < n - 1; i++) { lastSwapIndex = 0; for (int j = 0; j < rightBoundary; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } rightBoundary = lastSwapIndex; if (rightBoundary <= 1) { break; } } }
第五種寫法:優化外層循環和內層循環
在第四種寫法的基礎上,我們可以發現每輪比較都會找到當前輪最大的元素,並將其放到了正確的位置。因此,我們可以在每輪比較中同時找到最大值和最小值,並進行排序。
public static void bubbleSort5(int[] arr) { int n = arr.length; int lastSwapIndex, leftBoundary, rightBoundary; leftBoundary = 0; rightBoundary = n - 1; while (leftBoundary < rightBoundary) { lastSwapIndex = 0; for (int j = leftBoundary; j < rightBoundary; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } rightBoundary = lastSwapIndex; for (int j = rightBoundary; j > leftBoundary; j--) { if (arr[j] < arr[j-1]) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; lastSwapIndex = j - 1; } } leftBoundary = lastSwapIndex; } }
以上就是五種常見的冒泡排序寫法,每種寫法都有不同的最佳化方式,在實際使用時可以根據具體情況選擇合適的寫法。透過這些最佳化,可以提高冒泡排序的效率,減少排序時間。
冒泡排序雖然簡單,但是對於大規模的資料排序時效能較差。因此,在實際應用中,更常使用更有效率的排序演算法,如快速排序、歸併排序等。
以上是一些常見的Java冒泡排序演算法:以升序排列的詳細內容。更多資訊請關注PHP中文網其他相關文章!