最后有改进版
前情提要
- 插入排序只在数据量小，数据有序程度较高的情况下效率高
- 基于上述这点，D.L.Shell于1959年提出了 "缩小增量排序"(Diminishing Increment Sort)，是一种插入排序的优化排序算法
核心思想
- 不同于插入算法，希尔算法引入了"增量"-gap，也可以理解为间隔，用处是，对数组进行按增量进行划分，对每个划分进行插入排序，这是为了满足插入排序高效的一个条件：数据量小
比如，
int[] nums = {4, 3, 5, 7, 6, 8, 9, 1, 2};
nums长度为9，最开始设置gap = nums.length / 2也就是gap = 4，此时数组划分为{4, 6, 2}, {3, 8}, {5, 9}, {7, 1}，第一组也就是nums[0] = 4，nums[0 + gap] = 6, nums[0 + 2 * gap] = 2，第二组就是nums[1] = 3, nums[1 + gap] = 8，后面以此类推，注意索引不要越界
然后对每个组进行插入排序，四个组排完分别是{2, 4, 6}, {3, 8}, {5, 9}, {1, 7}，此时数组nums = {2, 3, 5, 1, 4, 8, 9, 7, 6}可以明显看出比原始数组更符合插入排序高效的第二个条件：数据有序程度较高
- 注意：分组只是逻辑上的分组，在实际操作中只是特殊处理索引，比如遍历一个分组，
for (int i = 0; i < nums.length; i += gap)类似于这样，把gap当成"步长"去遍历数组，就能"分出"每个组 - 第一次分组插入排序之后，把步长
gap /= 2砍掉一半，这样一下，下一轮每个分组的元素数量就翻倍(考虑到奇数个，所以只能是近似翻倍)
接着例子，第二轮分组，
{2, 5, 4, 9, 6}, {3, 1, 8, 7}，分组插入排序后{2, 4, 5, 6, 9}, {1, 3, 7, 8}，数组{2, 1, 4, 3, 5, 7, 6, 8, 9}，而第三轮时步长gap = 1就变成普通插入排序，但这是数据有序性较高，所以性能提高不少
算法实现
完整代码
- 建议先复制完整代码再对照着看具体步骤
public class ShellSortDemo {
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private static void shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.length; i++) {
for (int j = i; j >= gap; j -= gap) {
if (nums[j] < nums[j - gap]) {
swap(nums, j, j - gap);
} else {
break;
}
}
}
}
}
public static void main(String[] args) {
// int[] nums = {4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8};
int[] nums = new int[2000000];
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
// System.out.println(Arrays.toString(nums));
long startTime = System.currentTimeMillis();
shellSort(nums);
long endTime = System.currentTimeMillis();
System.out.println("耗时: " + (endTime - startTime) + "ms" );
// System.out.println(Arrays.toString(nums));
}
}
具体步骤
整个过程其实在草稿纸上用一个简单数组写一下过程就很清晰了
-
void swap(int[] nums, int i, int j)是辅助方法，用于交换两个数 -
void shellSort(int[] nums)是算法主体-
for (int gap = nums.length / 2; gap > 0; gap /= 2)最外层循环，设置每一次大循环的步长，更新时砍掉一半，直到步长为0 -
for (int i = gap; i < nums.length; i++)第二层循环结合for (int j = i; j >= gap; j -= gap)第三层循环就是对每个分组进行插入排序- 比如还是这个数组
{4, 3, 5, 7, 6, 8, 9, 1, 2}，i = gap(i = 4), j = i = 4，此时就是对第一个分组{4, 6, 2}进行插入排序的第一次，通过判段if (nums[j] < nums[j - gap])也就是比较第一个组的4和6，如果后者小，就交换两者位置swap(nums, j, j - gap)，否则跳出最内层循环，因为此时第一个分组的第一次插入排序已经完成 - 然后
i++ == 5, j = i = 5，也就是对第二个分组{3, 8}进行插入排序，后面i更新后执行的操作以此类推 - 等到第二层循环的
i = 8，第三层j = i = 8，则是第一组接着第一次插入排序后的第二次，这时会比较2和6，发现两者需要交换，交换后再比较4和2发现又得交换，然后第一分组的插入排序就完成了
- 比如还是这个数组
-
测试
用随机生成的数据进行测试，取平均值
4万个数据，用时9-13毫秒
40万个数据，用时90-110毫秒
400万个数据，用时1300-1500毫秒
4000万个数据，用时16000-20000毫秒(16-20秒)
而插入排序
4万个数据，用时900-1000毫秒
40万个数据，用时76000-100000毫秒(70多到100秒)
数量级再往上都没那个耐心等它跑完了
明显看到希尔排序的效率是高很多很多
再测试了一下快速排序，堆排序这两种平均时间复杂度是
O(n*logn)的排序算法，发现希尔排序与这两种算法用时几乎是一样的，不过希尔排序的平均时间复杂度至今仍不能给出确定的答案(O(n*logn), O(n^(1.3)), O(n^(1.5)))，所以就先不管了
---------------------------华丽的分割线---------------------------------
用类似于上篇文章 插入排序 后面所讲的改进，将希尔排序修改为以下实现，性能提高到原来的
140% - 200%
private static void shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.length; i++) {
int insertValue = nums[i];
int insertIndex = i - gap;
while (insertIndex >= 0 && nums[insertIndex] > insertValue) {
nums[insertIndex + gap] = nums[insertIndex];
insertIndex -= gap;
}
if (insertIndex != i - gap) {
nums[insertIndex + gap] = insertValue;
}
}
}
}
