选择排序法
- 每轮循环都找出最小的那一个。
- 可以进行原地排序。
- 内存循环找出最小的那个。
- 外层循环控制初始查找的值。
网络异常，图片无法展示
|
算法实现
- 找出循环不变量。
arr[0...i)是有序的，arr[i...n)是无序的。
- 泛型必须实现Comparable接口。所以自定义类必须实现Comparable接口。并重写compareTo方法。
- swap函数是交换数组中的元素，要传入数组。
- 内层循环是比较当前位置的值和minIndex位置的值的大小关系，不是i位置的大小关系。
// 泛型必须实现Comparable接口。 public static <E extends Comparable<E>> E[] sort(E[] arr) { // arr[0...i)是有序的，arr[i...n)是无序的。 for(int i = 0; i < arr.length; i++) { // 假设每次循环的第一个元素为最小 int minIndex = i; for(int j = i + 1; j < arr.length; j++) { if(arr[minIndex].compareTo(arr[j]) >= 0) { minIndex = j; } } // 交换查找到的最小元素和开始元素的位置 swap(arr, i, minIndex); } return arr; } // 这个方法是交换数组中两个元素的位置，而非两个元素值，那么会出错。 private static <E extends Comparable<E>> void swap(E[] arr, int i, int minIndex) { E t = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = t; }
复杂度分析
网络异常，图片无法展示
|
测试结果
- 当测试数组长度增大10倍，那么时间复杂度是大约100倍。
网络异常，图片无法展示
|
插入排序法
- 每轮循环都和当前外层循环下标之前的元素比较。
- 可以进行原地排序。
- 内存循环排序
arr[0, i)之间的数字。
- 外层循环控制比较范围的最大下标。
算法实现
public static <E extends Comparable<E>> E[] sort(E[] arr) { for(int i = 0; i < arr.length; i++) { // 循环不变量，arr[0, i)已排好序， arr[i, n)未排序。 for(int j = i; j > 0; j--) { // 和j < i 之前的元素都比较一下。直到遇到前面最小的一个 if(arr[j].compareTo(arr[j - 1]) <= 0) { swap(arr, j, j - 1); }else { break; } } } return arr; } private static <E> void swap(E[] arr, int i, int minIndex) { E t = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = t; }
复杂度分析
网络异常，图片无法展示
|
算法小优化
我们知道上面的算法是和前一个元素比较，如果符合条件就换位置。但是我们其实没有必要每次比较都换位置。直接平移满足条件的元素即可。先保存当前比较的元素。找到合适的位置，直接将其赋值即可。
public static <E extends Comparable<E>> E[] sort(E[] arr) { for(int i = 0; i < arr.length; i++) { // 循环不变量，arr[0, i)已排好序， arr[i, n)未排序。 E current = arr[i]; int j; for(j = i; j - 1 >= 0; j--) { if(current.compareTo(arr[j - 1]) < 0) { arr[j] = arr[j - 1]; }else { break; } } // 在外层循环确定位置。 arr[j] = current; } return arr; }
这个优化，并不能降低时间复杂度。
网络异常，图片无法展示
|
一个重要的特征
如果数组是有序的，那么内层循环将指示比较一下前面一个元素而已，然后就会结束。
网络异常，图片无法展示
|
对比插入和选择排序算法
网络异常，图片无法展示
|
以上测试的工具类
- ArrayGenerator是提供生成有序和无序数组的函数。
public class ArrayGenerator { // 生成一个有序数组，指定长度 public static Integer[] generateOrderedArray(int n) { Integer[] arr = new Integer[n]; for(int i = 0; i < n; i++) { arr[i] = i; } return arr; } // 生成一个无序数组，指定其长度 public static Integer[] generateRandomArray(int n, int bound) { Integer[] arr = new Integer[n]; Random random = new Random(); for(int i = 0; i < n; i++) { arr[i] = random.nextInt(bound); } return arr; } }
- SortingHelper为了测试算法所需时间。
public class SortingHelper { // 判断数组是否有序 public static <E extends Comparable<E>> boolean isSorted(E[] arr) { for(int i = 1; i < arr.length; i++) { if(arr[i - 1].compareTo(arr[i]) > 0) { return false; } } return true; } // 测试各种排序组合时间复杂度 public static <E extends Comparable<E>> void sortTest(String className, E[] arr) { try { // Class aClass = Class.forName(className); // System.out.println(aClass); // Method sort = aClass.getDeclaredMethod("sort"); // sort.setAccessible(true); long start = System.nanoTime(); if(className.equals("SelectSort")) { SelectSort.sort(arr); }else if(className.equals("InsertSort")) { InsertSort.sort(arr); }else if(className.equals("InsertSort1")) { InsertSort.sort1(arr); }; // sort.invoke(aClass, arr); long end = System.nanoTime(); double time = (end - start) / 1000000000.0; if(!SortingHelper.isSorted(arr)) { throw new RuntimeException(className + "failed"); } System.out.println(String.format("%s, n=%d : %fs", className, arr.length, time)); } catch (Exception e) { e.printStackTrace(); } } }
