希尔排序(ShellSort)
概念介绍
希尔排序(ShellSort): 是插入排序的变种，又称缩小增量排序(Diminishing Increment Sort), 是直接插入排序算法的一种更高效的改进版本。 希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是基于插入排序的以下两点性质而提出改进方法的，通过减少了其复制的次数，提高排序效率
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序是按照不同步长对元素进行插入排序
当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
排序思路
将整个序列按照相距某个“增量”进行拆分，然后逐个对子序列进行增量插入排序，使得得到的结果基本有序，最后对基本有序的序列进行一次直接插入排序，使得整个序列有序
排序的关键
希尔排序的关键是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。 “增量”的选取是最关键的，下面的源码示例中是以gap=gap/2的方式选取增量的
究竟应该选取什么样的 增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。 不过大量的研究表明，当增量序列为dlta[k]=2t-k+1-1（0≤k≤t≤⌊log2(n+1)⌋）时，可以获得不错的效率。需要注意的是，增量序列的最后一个增量值必须等于1才行
适用场景
希尔排序的时间的时间复杂度： 所以，希尔排序的时间复杂度会比o(n^2)好一些
希尔排序没有快速排序算法快 O(n(logn))，在中等大小规模表现良好
希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。 专家们提倡：几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法
源码示例
public class ShellSortExample{
public static void main(String[] args) {
int arr[] = {12, 34, 54, 2, 3};
shellSort(arr);
print(arr);
}
public static int shellSort(int arr[]) {
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (int i = gap; i < n; i += 1) {
// add a[i] to the elements that have been gap sorted save a[i] in temp and make a hole at position i
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// put temp (the original a[i]) in its correct location
arr[j] = temp;
}
}
return 0;
}
static void print(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}