1. 十大排序算法
其中 冒泡，选择，归并，快速，希尔，堆排序属于比较排序
稳定性理解
如果相等的两个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法。
排序前：5，1，3(a)，4，7，3(b)
稳定的排序：1，3(a)，3(b)，4，5，7
不稳定的排序：1，3(b)，3(a)，4，5，7
原地算法（In-place Algorithm）理解
定义：不依赖额外的资源或依赖少数的额外资源（空间复杂度较低），仅依靠输出覆盖输入（例如直接对输入的数组进行操作）
2. 工具类用于提供测试数据与测试代码正确性
2.1 断言工具类 public class Asserts { public static void test(boolean value) { try { if (!value) throw new Exception("测试未通过"); } catch (Exception e) { e.printStackTrace(); } } } 2.2 Integers工具类 public class Integers { /** 生成随机数 */ public static Integer[] random(int count, int min, int max) { if (count <= 0 || min > max) return null; Integer[] array = new Integer[count]; int delta = max - min + 1; for (int i = 0; i < count; i++) { array[i] = min + (int)(Math.random() * delta); } return array; } /** 合并两个数组 */ public static Integer[] combine(Integer[] array1, Integer[] array2) { if (array1 == null || array2 == null) return null; Integer[] array = new Integer[array1.length + array2.length]; for (int i = 0; i < array1.length; i++) { array[i] = array1[i]; } for (int i = 0; i < array2.length; i++) { array[i + array1.length] = array2[i]; } return array; } public static Integer[] same(int count, int unsameCount) { if (count <= 0 || unsameCount > count) return null; Integer[] array = new Integer[count]; for (int i = 0; i < unsameCount; i++) { array[i] = unsameCount - i; } for (int i = unsameCount; i < count; i++) { array[i] = unsameCount + 1; } return array; } /** * 生成头部和尾部是升序的数组 * disorderCount：希望多少个数据是无序的 */ public static Integer[] headTailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int begin = (array.length - disorderCount) >> 1; reverse(array, begin, begin + disorderCount); return array; } /** * 生成中间是升序的数组 * disorderCount：希望多少个数据是无序的 */ public static Integer[] centerAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int left = disorderCount >> 1; reverse(array, 0, left); int right = disorderCount - left; reverse(array, array.length - right, array.length); return array; } /** * 生成头部是升序的数组 * disorderCount：希望多少个数据是无序的 */ public static Integer[] headAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, array.length - disorderCount, array.length); return array; } /** * 生成尾部是升序的数组 * disorderCount：希望多少个数据是无序的 */ public static Integer[] tailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, 0, disorderCount); return array; } /** 升序生成数组 */ public static Integer[] ascOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = min++; } return array; } /** 降序生成数组 */ public static Integer[] descOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = max--; } return array; } /** 反转数组 */ private static void reverse(Integer[] array, int begin, int end) { int count = (end - begin) >> 1; int sum = begin + end - 1; for (int i = begin; i < begin + count; i++) { int j = sum - i; int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } /** 复制数组 */ public static Integer[] copy(Integer[] array) { return Arrays.copyOf(array, array.length); } /** 判断数组是否升序 */ public static boolean isAscOrder(Integer[] array) { if (array == null || array.length == 0) return false; for (int i = 1; i < array.length; i++) { if (array[i - 1] > array[i]) return false; } return true; } /** 打印数组 */ public static void println(Integer[] array) { if (array == null) return; StringBuilder string = new StringBuilder(); for (int i = 0; i < array.length; i++) { if (i != 0) string.append("_"); string.append(array[i]); } System.out.println(string); } } 2.3 时间测试工具类 public class Times { private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS"); public interface Task { void execute(); } public static void test(String title, Task task) { if (task == null) return; title = (title == null) ? "" : ("【" + title + "】"); System.out.println(title); System.out.println("开始：" + fmt.format(new Date())); long begin = System.currentTimeMillis(); task.execute(); long end = System.currentTimeMillis(); System.out.println("结束：" + fmt.format(new Date())); double delta = (end - begin) / 1000.0; System.out.println("耗时：" + delta + "秒"); System.out.println("-------------------------------------"); } } 2.4 Sort抽象父类 public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> { /** 目标数组 */ protected T[] array; /** 比较次数 */ private int cmpCount; /** 交换次数 */ private int swapCount; /** 执行时间 */ private long time; /** 小数格式化 */ private DecimalFormat fmt = new DecimalFormat("#.00"); /** 预处理 */ public void sort(T[] array) { if (array == null || array.length < 2) return; this.array = array; long begin = System.currentTimeMillis(); sort(); time = System.currentTimeMillis() - begin; } /** 目标方法 */ protected abstract void sort(); /** * 比较数组下标对应的值 * * 返回值等于0，代表 array[index1] == array[index2] * 返回值小于0，代表 array[index1] < array[index2] * 返回值大于0，代表 array[index1] > array[index2] */ protected int cmp(int index1, int index2) { cmpCount++; return array[index1].compareTo(array[index2]); } /** 比较值 */ protected int cmp(T value1, T value2) { cmpCount++; return value1.compareTo(value2); } /** 交换值 */ protected void swap(int index1, int index2) { swapCount++; T tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; } /** 稳定性测试 */ @SuppressWarnings("unchecked") private boolean isStable() { Student[] students = new Sort.Student[20]; for (int i = 0; i < students.length; i++) { //（0，10） （10，10） （20，10） （30，10） students[i] = new Student(i * 10, 10); } sort((T[]) students);//只会对年龄进行排序 for (int i = 1; i < students.length; i++) { int score = students[i].score; int prevScore = students[i - 1].score; if (score != prevScore + 10) return false; } return true; } private static class Student implements Comparable<Student>{ Integer score; Integer age; public Student(Integer score, Integer age) { this.score = score; this.age = age; } @Override public int compareTo(Student o) { return age - o.age; } } /** 排序方式 */ @Override public int compareTo(Sort o) { int result = (int)(time - o.time); if(result != 0) return result; result = cmpCount - o.cmpCount; if(result != 0) return result; return swapCount - o.swapCount; } @Override public String toString() { return "【" + getClass().getSimpleName() + "】\n" + "交换次数 ==> " + numberString(swapCount) + "\n" + "比较次数 ==> " + numberString(cmpCount) + "\n" + "执行时间 ==> " + time * 0.001 + "s" + "\n" + "稳定性 ==> " + isStable() + "\n" + "================================="; } /** 数字格式化 */ private String numberString(int number) { if (number < 10000) return "" + number; if (number < 100000000) { return fmt.format(number / 10000.0) + "万"; } return fmt.format(number / 100000000.0) + "亿"; } } 3. 冒泡排序（Bubble Sort） 3.1 执行流程从头开始比较每一对相邻元素，如果第一个比第二个大就交换它们的位置。执行完一轮后最末尾哪个元素就是最大的元素