希尔排序的改进是，使用一个增量将数组切分不同的分组，然后在组内进行插入排序，递减增量，直到增量为 1，好处就是数据能跨多个元素移动，一次比较就可能消除多个元素的交换。基本过程如下：
选取一个递增序列，一般使用x/2或者x/3+1
使用序列中最大的增量，对数组分组，在组内插入排序，递减增量，直到为 1
核心代码：
public static void shellSort(int[] a, int n) { // 计算递增序列，3x+1 : 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < n/3) h = 3*h + 1; while (h >= 1) {// 直到间隔为 1 // 按间隔 h 切分数组 for (int i = h; i < n; i++) { // 对 a[i], a[i-h], a[i-2*h], a[i-3*h]...使用插入排序 int x = a[i]; // 待插入元素 int j=i; while (j >=h && x < a[j-h]) { a[j] = a[j-h];// 为待插入元素腾地 j -= h; } a[j] = x; // 插入 x } // 递减增量 h /= 3; } }希尔排序数组拆分插入图解，上面的动图可以辅助理解，与下图数据不一致：
算法分析：
时间复杂度与选择的增量序列有关，可能的值时 O(n^2) > O(n^1.5) > O(nlg2n)
空间复杂度 O(1)
不稳定的排序算法
5. 归并排序（递归&非递归）归并排序是分而治之的排序算法，基本思想是：将待排序序列拆分多个子序列，先使每个子序列有序，再使子序列间有序，最终得到完整的有序序列。归并排序本质就是不断合并两个有序数组的过程，实现时主要分为两个过程：
拆分 - 递归的将当前数组二分（如果N是偶数，两边个数平等，如果是奇数，则一边多一个元素），直到只剩 0 或 1 个元素
归并 - 分别将左右半边数组排序，然后归并在一起形成一个大的有序数组
二路归并递归实现，核心代码：
public static void mergeSort(int[] a, int low, int high) { // 要排序的数组 a[low..high] if (low < high) {// 是否还能再二分 low >= high (0 或 1 个元素) int mid = low + (high - low) / 2; // 取中间值，避免 int 溢出 mergeSort(a, low, mid); // 将左半边排序 mergeSort(a, mid + 1, high); // 将右半边排序 merge(a, low, mid, high); // 归并左右两边 } } public static void merge(int[] a, int low, int mid, int high) { int n = high - low + 1; // 合并后元素总数 int[] b = new int[n]; // 临时合并数组 int left = low, // 左边有序序列起始下标 right = mid + 1, // 右边有序序列起始下标 bIdx = 0; // 按升序归并到新数组 b 中 while (left <= mid && right <= high) { b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++]; } // 右边序列已拷贝完毕，左边还有剩余，将其依次拷贝到合并数组中 while (left <= mid) { b[bIdx++] = a[left++]; } // 左边序列已拷贝完毕，右边还有剩余，将其依次拷贝到合并数组中 while (right <= high) { b[bIdx++] = a[right++]; } // 将归并后的数组元素拷贝到原数组适当位置 for (int k = 0; k < n; k++) { a[low + k] = b[k]; } }数组拆分和方法调用的动态情况如下图(右键查看大图)：
递归的本质就是压栈，对于 Java 来说，调用层次太深有可能造成栈溢出。一般的，递归都能转为迭代实现，有时迭代也是对算法的优化。
归并排序中的递归主要是拆分数组，所以，非递归的重点就是把这部分改成迭代，它们的终止条件不同：
递归是在遇到基本情况时终止，比如遇到了两个各包含1个元素的数组，从大数组到小数组，自顶向下
迭代则相反，自底向上，它首先按 1 切分保证数组中的每2个元素有序，然后按 2 切分，保证数组中的每4个元素有序，以此类推，直到整个数组有序