作者: whooyun发表于: 2023-03-29 13:43
open API 生成的冒泡排序及优化方案
public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; bubbleSort(arr); for (int i : arr) { System.out.print(i + " "); } } public static void bubbleSort(int[] arr) { int temp; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } } //添加标记优化,一种优化方法是添加一个标记,记录每一轮是否进行了交换 //如果没有进行交换,则说明已经排好序,可以直接结束排序。这样可以避免不必要的比较和交换,提高排序效率。 public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; bubbleSort(arr); for (int i : arr) { System.out.print(i + " "); } } public static void bubbleSort(int[] arr) { int temp; boolean flag = true; // 添加标记 for (int i = 0; i < arr.length - 1 && flag; i++) { flag = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; // 发生了交换 } } } } } //每轮排序中记录最后一次交换的位置 //该位置之后的元素已经有序,下一轮排序时只需要比较到该位置即可。这样可以进一步减少比较和交换的次数,提高排序效率。 public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; bubbleSort(arr); for (int i : arr) { System.out.print(i + " "); } } public static void bubbleSort(int[] arr) { int temp; int lastExchangeIndex = 0; // 记录最后一次交换的位置 int sortBorder = arr.length - 1; // 无序数列的边界 for (int i = 0; i < arr.length - 1; i++) { boolean flag = true; for (int j = 0; j < sortBorder; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = false; lastExchangeIndex = j; } } sortBorder = lastExchangeIndex; if (flag) { break; } } } } //鸡尾酒排序(双向冒泡排序) //鸡尾酒排序先从左到右进行冒泡排序,然后再从右到左进行冒泡排序,如此交替进行,可以让排序更快地逼近最终状态 public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; cocktailSort(arr); for (int i : arr) { System.out.print(i + " "); } } public static void cocktailSort(int[] arr) { int temp; int left = 0; int right = arr.length - 1; while (left < right) { for (int i = left; i < right; i++) { // 从左到右冒泡 if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } right--; for (int i = right; i > left; i--) { // 从右到左冒泡 if (arr[i] < arr[i - 1]) { temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } } left++; } } }