Java实现的冒泡排序改进版

这种实现方式的冒泡排序最好的情况下只需要O(n)的复杂度，最坏的情况下依然是O(n^2)的复杂度

/** * 冒泡排序（从小到大） * 从左到右不断遍历，将相邻且逆序（大, 小）的元素交换（小, 大） * 一轮循环后，最大的元素被上浮到最右侧 * 除去最后一个元素，剩下的数组继续如上操作 * 如果有一轮循环没有发生交换操作，则说明数组已经有序，终止循环 * * @Author Nino 2019/10/2 */ import java.util.Arrays; import java.util.Random; public class BubbleSort<E extends Comparable<E>> extends Sort<E> { public void sort(E[] arr) { int length = arr.length; //检测是否已经是有序数组 boolean isSorted = false; //当数组是有序数组时终止循环 for (int i = length - 1; i > 0 && !isSorted; i--) { isSorted = true; for (int j = 0; j < i; j++) { if (arr[j].compareTo(arr[j+1]) > 0) { swap(arr, j, j + 1); isSorted = false; } } } } /** * 交换数组nums中i，j索引的值 * @param nums * @param i * @param j */ private void swap(E[] nums, int i, int j) { E temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } /** * 测试用例 * @param args */ public static void main(String[] args) { Random random = new Random(); Integer[] arr = new Integer[10]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.valueOf(random.nextInt(20)); } System.out.println(Arrays.asList(arr).toString()); new BubbleSort<Integer>().sort(arr); System.out.println(Arrays.asList(arr).toString()); } }

用例输出：

[19, 4, 5, 5, 16, 9, 1, 19, 3, 19] [1, 3, 4, 5, 5, 9, 16, 19, 19, 19]