Java实现插入排序

插入排序（从小到大）

方法：从左向右遍历，每次将元素插入左侧已经排好序的数组中，使得插入后左侧数组依然有序，具体插入方式是采用相邻元素逆序交换的方式。因此如果数组部分有序，逆序较少，时间复杂度会较低；而如果数组是倒序的，逆序较多，时间复杂度会很高

插入排序的时间复杂度取决于数组的初始顺序：

最好的情况下，数组原先是有序的，需要$N-1$次比较，$O(n)$时间复杂度；最坏的情况下，数组是逆序的，需要$N^2/2$次比较和$N^2/2$次交换，$O(n^2)$时间复杂度；平均情况下，需要$N^2/4$次比较和$N^2/4$次交换。 import java.util.Arrays; import java.util.Random; public class InsertionSort<E extends Comparable<E>> { /** * 排序主体 * @param arr */ public void sort(E[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0 && !less(arr[j - 1], arr[j]); j--) { swap(arr, j-1, j); } } } /** * 给定a，b两元素大小的比较方式 * @param a * @param b * @return */ private boolean less(E a, E b) { return a.compareTo(b) < 0; } /** * 交换数组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 InsertionSort<Integer>().sort(arr); System.out.println(Arrays.asList(arr).toString()); } }

用例输出：

[8, 7, 19, 11, 7, 10, 12, 9, 8, 8] [7, 7, 8, 8, 8, 9, 10, 11, 12, 19]