一、简单的冒泡排序算法的实现
package BubbleSort; import MergeSort.ArrayGenerator; import MergeSort.SortingHelper; /** * @author DBC * @version 1.0 * @date 2022-02-12 13:49 */ public class BubbleSort { private BubbleSort() { } public static <E extends Comparable<E>> void sort(E[] data) { for (int i = 0; i + 1 < data.length; i++) { // arr[n - i,n)已排好序 // 通过冒泡在 arr[n - i -1] 位置放上合适的元素 for (int j = 0; j < data.length - i - 1; j++) { if (data[j].compareTo(data[j + 1]) > 0) { swap(data, j, j + 1); } } } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 20000; Integer[] arr = ArrayGenerator.generateRandomArray(n,n); SortingHelper.sortTest("BubbleSort",arr); } }
二、冒泡排序算法的优化
public static <E extends Comparable<E>> void sort2(E[] data) { for (int i = 0; i + 1 < data.length; i++) { // arr[n - i,n)已排好序 // 通过冒泡在 arr[n - i -1] 位置放上合适的元素 boolean isSwapped = false; for (int j = 0; j < data.length - i - 1; j++) { if (data[j].compareTo(data[j + 1]) > 0) { swap(data, j, j + 1); isSwapped = true; } } if (!isSwapped){ break; } } }
三、冒泡排序算法还能继续优化!
public static <E extends Comparable<E>> void sort3(E[] data) { for (int i = 0; i + 1 < data.length;) { // arr[n - i,n)已排好序 // 通过冒泡在 arr[n - i -1] 位置放上合适的元素 int lastSwappedIndex = 0; for (int j = 0; j < data.length - i - 1; j++) { if (data[j].compareTo(data[j + 1]) > 0) { swap(data, j, j + 1); lastSwappedIndex = j + 1; } } i = data.length - lastSwappedIndex; } }
老规矩,依然是同类对比!
public static void main(String[] args) { int n = 30000; Integer[] arr = ArrayGenerator.generateRandomArray(n,n); Integer[] arr2 = Arrays.copyOf(arr,arr.length); Integer[] arr3 = Arrays.copyOf(arr,arr.length); SortingHelper.sortTest("BubbleSort",arr); SortingHelper.sortTest("BubbleSort2",arr2); SortingHelper.sortTest("BubbleSort3",arr3); arr = ArrayGenerator.generateOrderedArray(n); arr2 = Arrays.copyOf(arr,arr.length); arr3 = Arrays.copyOf(arr,arr.length); SortingHelper.sortTest("BubbleSort",arr); SortingHelper.sortTest("BubbleSort2",arr2); SortingHelper.sortTest("BubbleSort3",arr3); }
本文作者为DBC,转载请注明。