三.插入排序（直接插入排序+希尔排序）
1.直接插入排序
根据比较类Comparator来判断是升序排列还是降序排列 若Comparator中的compare函数返回值是a > b ? 1 : (a < b ? -1 : 0)，则是升序排列 compare函数返回值是a > b ? -1 : (a < b ? 1 : 0)，则是降序排列
排序思路： ①假定数组第一个元素是有序序列，第二个元素到最后一个元素是无序序列 ②从无序序列最开始元素开始遍历 ③从有序序列一次从后往前比较，若发现不满足排序规则的元素，有序序列向后移动一位 ④重复③，知道找到该元素所在的位置 ⑤重复②~④
时间复杂度：O(n^2) 空间复杂度：O(1)
public static <T> void insertSort(T[] t, Comparator<? super T> comparator) { int size = t == null ? 0 : t.length; T temp; int j; for(int i = 1; i < size; i++) { temp = t[i]; for(j = i; j > 0; j--) { if(comparator.compare(temp, t[j - 1]) < 0) { t[j] = t[j - 1]; } else { break; } } t[j] = temp; } } 2.希尔排序根据比较类Comparator来判断是升序排列还是降序排列 若Comparator中的compare函数的返回值是：a > b ? 1 : (a < b ? -1 : 0)，则是升序排列 若compare函数的返回值是：a > b ? -1 : (a < b ? 1 : 0)，则是降序排列
排序思路: ①选择一个增量序列，增量序列最后一个为1 ②假设增量序列个数为k，则对排序序列进行k趟排序 ③每趟排序，根据对应的增量，将排序序列分成长度为m的子序列，对各自序列进行直接插入排序
时间复杂度：O(n^1.3) 空间复杂度：O(1)
public static <T> void shellSort(T[] t, Comparator<? super T> comparator) { int size = t == null ? 0 : t.length; int dk = size / 2; while(dk >= 1) { for(int i = dk; i < size; i++) { // 若第i个元素大于i-dk元素，直接插入。小于的话，移动有序表后插入 if(comparator.compare(t[i], t[i - dk]) < 0) { int j = i - dk; T temp = t[i]; // 临时存储待排序序列 while(comparator.compare(temp, t[j]) < 0) { t[j + dk] = t[j]; j -= dk; // 元素后移 if(j < 0) break; // 如果j小于0，则跳出此次循环 } t[j + dk] = temp; // 插入到正确位置 } } dk = dk / 2; } } 测试程序disturbOrder(T[] t)方法请查看Java算法-排序-交换排序
public static void main(String[] args) { Integer[] numbers = new Integer[9999]; for(int i = 0; i < numbers.length; i++) { numbers[i] = i; } disturbOrder(numbers); long start4 = System.currentTimeMillis(); insertSort(numbers, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return a > b ? 1 : (a < b ? -1 : 0); } }); long end4 = System.currentTimeMillis(); System.out.println("插入排序耗时:" + (end4 - start4)); disturbOrder(numbers); long start5 = System.currentTimeMillis(); shellSort(numbers, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return a > b ? 1 : (a < b ? -1 : 0); } }); long end5 = System.currentTimeMillis(); System.out.println("希尔排序耗时:" + (end5 - start5)); }