基本思想 先将待排序的数组元素分成多个子数组，使得每个子数组的元素个数相对较少，然后对各个子数组分别进行直接插入排序，待整个待排数组“基本有序”后，最后在对所有元素进行一次直接插入排序。 代码
public class ShellSort { public static void shellSort(int[] arrays) { int temple; if (arrays == null || arrays.length <= 1) { return; } // 增量 int incrementNum = arrays.length / 2; while (incrementNum >= 1) { for (int i = incrementNum; i < arrays.length; i++) { // 进行插入排序 for (int j = i; j >= incrementNum; j = j - incrementNum) { if (arrays[j] < arrays[j - incrementNum]) { temple = arrays[j]; arrays[j] = arrays[j - incrementNum]; arrays[j - incrementNum] = temple; } } } // 设置新的增量 incrementNum = incrementNum / 2; } } public static void main(String[] args) { int[] a = new int[] { 49, 38, 65, 97, 76, 13, 27, 50 }; shellSort(a); for (int i : a) System.out.print(i + " "); } }时间复杂度 O(n)——–最好 O(n^2)—–最坏 O(nlog2n)–平均
