插入+希尔排序

插入排序：

将待排序数组分为有序数组和无序数组，遍历无序数组依次插入到有序数组中。重点在于将元素与无序数组比较时，在找到插入位置前依次将无序数组后移，来为元素腾出位置。

void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int j;
            int cur = nums[i];　　//作为tmp保存待插入元素，后移的过程会将该元素覆盖
            for (j = i - 1; j >= 0; j--) {
                if (nums[j] > cur)
                    nums[j + 1] = nums[j];
                else
                    break;
            }
            nums[j + 1] = cur;
        }
    }

插入排序对基本有序效率较高。 当有大规模数据或者小元素大量集中在无序数组的靠后位置时，就需要多次移动才能将其拍到有序数组前列。

希尔排序又称缩小增量排序，当gap减小为1时即为插入排序。关于性能优劣见文末链接，这里讨论一下代码实现。

对于分组后插入排序的实现，没必要套两次循环，即分别对gap个数组排序。由于各个数组之间互不干扰，可以直接遍历，更加简洁。

void shellSort(int[] nums) {
        for (int gap = nums.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                int cur = nums[i];
                while (i - gap >= 0 && cur < nums[i - gap]) {
                    nums[i] = nums[i - gap];
                    i -= gap;
                }
                nums[i] = cur;
            }
        }
    }

参考原文