冒泡排序
算法描述算法实现进一步优化 选择排序
算法描述算法实现与冒泡排序比较 冒泡排序 算法描述 依次比较数组中相邻两个元素大小，若 a[j] > a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后重复以上步骤，直到整个数组有序 算法实现
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; } }}
优化点1：每经过一轮冒泡，内层循环就可以减少一次优化点2：如果某一轮冒泡没有发生交换，则表示所有数据有序，可以结束外层循环 进一步优化
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)
选择排序一般要快于冒泡，因为其交换次数少
但如果集合有序度高，冒泡优于选择
冒泡属于稳定排序算法，而选择属于不稳定排序
稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序不稳定排序则反之