希尔排序
- 此算法建立在其他排序算法上（插入、冒泡等），但依据希尔排序的特性使用插入排序会更加高效。
- 首先，将要排序的数组，按照一定的增量分出子序列，我们对子序列利用插入排序算法排序。
- 然后，增量=增量/2（自己按照实际情况设置增量），在按照增量分出子序列，对它们进行排序。
- 如此往复，直到增量=1时，就像普通数组（但此时的数组比原数组更有序）那样进行最后一次插入排序（在有序性大的数组使用插入排序更好）后即可结束。
- 增量可以看作子序列中各个节点的距离，以及子序列的个数。
图解
来自网上
代码模板
public void ShellSort() {
int[] arr = new int[]{3, 4, 5, 2, 1, 7, -1, 9, 0};
//增量
int incre = arr.length / 2;
while (incre != 0) {
//根据增量分出子序列，遍历各个子序列，开始插入排序
for (int i = 0; i < incre; i++) {
//对子序列利用插入排序算法进行排序
//编写该循环需注意每个子序列的第一个值的位置，以及同一个序列中各个节点的距离
for (int j = i + incre; j < arr.length; j += incre) {
//编写该循环需注意同一个序列中各个节点的距离
for (int k = j - incre; k >= 0; k -= incre) {
if (arr[k] > arr[k + incre]) {
int tmp = arr[k];
arr[k] = arr[k + incre];
arr[k + incre] = tmp;
} else break;
}
}
}
//增量每次除以2，增量为1且又进行过插入排序时，表示数组已经有序
incre /= 2;
}
for (int i : arr) {
System.out.println(i);
}
}
总结
希尔排序是插入排序的变种，这并不意味着希尔排序的效率一定比插入排序高。
在进行测试时，用到测试案例数据规模不够大，或者有序程度高，则可能运行效率反而比插入排序低。
- 那么希尔排序的优点是什么呢？
首先回顾以下希尔排序的流程，它会先将原数组分为一个个子序列，再将这些子序列进行排序。
注意这些子序列中的各个节点距离随着数据规模增大而增大，因此子序列的排序，我们可以花费很少的代价将位于数组末尾的数小的值（假定构造升序数组）移动到前面。
因此希尔排序的数值交换次数会比插入排序少很多。 - 在上面所说的层面上来看：数据规模越大，其效率与插入排序相比更加优秀。但其并不稳定，依赖原数组的具体情况。
希 尔 排 序 ： 空 间 复 杂 度 O ( 1 ) ， 其 时 间 复 杂 度 需 要 看 你 增 量 怎 么 取 希尔排序 ：空间复杂度O(1)，其时间复杂度需要看你增量怎么取 希尔排序：空间复杂度O(1)，其时间复杂度需要看你增量怎么取
那到底增量怎么取，希尔排序算法才能达到最优呢？
