插入排序
public static int[] sort(int[] a) { int length = a.length; for (int i = 1; i < length; i++) { int key = a[i]; int j = i - 1; // 此处为什么是j>=0呢?因为当j=0时如果还符合a[j]>key则还需要进行移位操作。 while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } // 在这里为什么是j+1呢,由于在while循环里最后一条语句j--。 a[j + 1] = key; } return a; }
希尔排序
public class ShellSort { static public int[] Sort(int[] a) { int len = a.length; int dk = len / 2; while (dk >= 1) { //System.out.println(dk); shellInsert(a, dk); dk /= 2; } return a; } /** * dk = 1,即简单插入排序 */ private static void shellInsert(int[] a, int dk) { if(dk == 0) throw new IllegalArgumentException("dk can't eqauls 0!"); int len = a.length; for (int i = dk; i < len; i++) { int key = a[i]; int j = i - dk; while (j >= 0 && key < a[j]) { a[j + dk] = a[j]; j-=dk; } a[j + dk] = key; } } }
对于希尔排序的dk的讨论较多可以查阅相关书籍。
二分插入排序
public class BinaryInsertionSort { public static int[] sort(int[] a) { int length = a.length; for (int i = 1; i < length; i++) { int key = a[i]; int low = 0; int high = i - 1; high = getInsertIndex(a, a[i], low, high); for (int j = i - 1; j >= high; j--) a[j + 1] = a[j]; a[high] = key; } return a; } private static int getInsertIndex(int[] a, int key, int low, int high) { while (low <= high) { int mid = (low + high) / 2; if (key > a[mid]) { low = mid + 1; } else { high = mid - 1; } } return high + 1; } }