常见的插入排序有直接插入排序、折半插入排序和希尔排序三种。接下来我就将这三种的实现附代码如下：
package com.xqq.插入排序; public class Sort<T> { @SuppressWarnings("unchecked") public void insertSort(T[] arrays) { if (arrays == null || arrays.length <= 1) return; int i, j; for (i = 1; i < arrays.length; i++) { // 有序区的数据后移而占用了该记录，所以用temp保存 // 用于比较，T需要实现Comparable接口 Comparable<? super T> temp = (Comparable<? super T>) arrays[i]; for (j = i - 1; j >= 0; j--) { int cmp = temp.compareTo(arrays[j]); if (cmp >= 0) { //找到插入位置退出循环 break; } // 有序区的元素大于待插入的元素 System.out.println("arrays[" + (j) + "]=" + arrays[j] + "->arrays[" + (j + 1) + "]= " + arrays[j+1]); arrays[j + 1] = arrays[j]; // 将该有序区的元素后移一位 } arrays[j + 1] = (T) temp; } } // 在查找插入位置时，对有序区使用折半查找，提高查找效率 // 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍为O(n^2) @SuppressWarnings("unchecked") public void binaryInsertSort(T[] arrays){ if(arrays == null || arrays.length <= 1) return; int i, j, low, high, mid; for(i = 1; i < arrays.length; i++){ Comparable<? super T> temp = (Comparable<? super T>) arrays[i]; low = 0; high = i - 1; // 利用折半查找找到插入点 while(low <= high){ mid = (low + high) / 2; int cmp = temp.compareTo(arrays[mid]); if(cmp < 0) high = mid - 1; else low = mid + 1; } // 移动 for(j = i - 1; j >= high + 1; j--) arrays[j + 1] = arrays[j]; // 插入 arrays[high + 1] = (T) temp; } } // 希尔排序, d 为增量 @SuppressWarnings("unchecked") private void shellPass(T [] arrays, int d){ if(arrays == null || arrays.length <= 1) return; int i, j; for(i = d; i < arrays.length; i++){ Comparable<? super T> temp = (Comparable<? super T>) arrays[i]; for(j = i - d; j >= 0; j -= d){ int cmp = temp.compareTo(arrays[j]); if(cmp >= 0) break; arrays[j + d] = arrays[j]; } arrays[j + d] = (T) temp; } } // 希尔排序 public void shellSort(T [] arrays, int [] d){ for(int i = 0; i < d.length; i++) shellPass(arrays, d[i]); } } 测试代码： package com.xqq.插入排序; import java.util.Arrays; public class Main { public static void main(String[] args) { Integer [] arrays = {4, 5, 7, 3, 3, 2, 1}; int [] d = {5, 3, 1}; Sort<Integer> sort = new Sort<Integer>(); System.out.println(Arrays.asList(arrays).toString()); // sort.insertSort(arrays); // sort.binaryInsertSort(arrays); sort.shellSort(arrays, d); System.out.println(Arrays.asList(arrays).toString()); } }