public static void bubble(int[] a) { for (int j = 0; j < a.length - 1; j++) { // 一轮冒泡 boolean swapped = false; // 是否发生了交换 for (int i = 0; i < a.length - 1 - j; i++) { System.out.println("比较次数" + i); if (a[i] > a[i + 1]) { Utils.swap(a, i, i + 1); swapped = true; } } System.out.println("第" + j + "轮冒泡" + Arrays.toString(a)); if (!swapped) { break; } } }
public static void bubble_v2(int[] a) { int n = a.length - 1; while (true) { int last = 0; // 表示最后一次交换索引位置 for (int i = 0; i < n; i++) { System.out.println("比较次数" + i); if (a[i] > a[i + 1]) { Utils.swap(a, i, i + 1); last = i; } } n = last; System.out.println("第轮冒泡" + Arrays.toString(a)); if (n == 0) { break; } } }
将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子集
重复以上步骤,直到整个数组有序
public static void selection(int[] a) { for (int i = 0; i < a.length - 1; i++) { // i 代表每轮选择最小元素要交换到的目标索引 int s = i; // 代表最小元素的索引 for (int j = s + 1; j < a.length; j++) { if (a[s] > a[j]) { // j 元素比 s 元素还要小, 更新 s s = j; } } if (s != i) { swap(a, s, i); } System.out.println(Arrays.toString(a)); } }
二者平均时间复杂度都是 O ( n 2 ) O(n^2) O(n2)
选择排序一般要快于冒泡,因为其交换次数少
但如果集合有序度高,冒泡优于选择
冒泡属于稳定排序算法,而选择属于不稳定排序