希尔排序
百度百科：
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的[关键词]越来越多，当增量减至 1 时，整个文件恰被分成一组，[算法]便终止。
希尔序动图：
代码实现：
步骤一:
因为希尔排序就是插入排序的增强版，所以第一步就是先写一个插入排序代码
代码实现：
/**
* 步骤一：实现一个插入排序
*/
public static void T1(){
int[] arr = {49,38,65,97,76,13,27,49,55,4};
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j]<arr[j-1]; j--) {
swap(arr,j,j-1);
}
}
System.out.println(Arrays.toString(arr));
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private static void swap(int[] arr ,int i, int j){
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
运行结果：
看到正确的执行结果
步骤二：
间隔排序：是希尔排序最核心的一步。
下面以 5 为间隔，对数组进行排序，对步骤一的代码进行改进。
代码实现：
/**
* 步骤二：在步骤一上进行改进，以 5 为间隔进行排序
*/
public static void T2(){
int[] arr = {49,38,65,97,76,13,27,49,55,4};
int gap = 5;
for (int i = gap; i < arr.length; i++) {
for (int j = i; j > gap-1 && arr[j]<arr[j-gap]; j-=gap) {
swap(arr,j,j-gap);
}
}
System.out.println(Arrays.toString(arr));
}
运行结果：
看到以5为间隔，进行了排序
步骤三：
希尔排序就是进行多次间隔排序，直到间隔为 1 完成最后的排序。
现在对步骤二的代码进行改进，完成最后的排序。
代码实现：
/**
* 步骤三：依次间隔变小，进行排序
*/
public static void T3(){
int[] arr = {49,38,65,97,76,13,27,49,55,4};
int gap = 5;
while (gap>=1){
for (int i = gap; i < arr.length; i++) {
for (int j = i; j > gap-1 && arr[j]<arr[j-gap]; j-=gap) {
swap(arr,j,j-gap);
}
}
System.out.println("以间隔为"+gap+"进行排序："+Arrays.toString(arr));
gap-=2;
}
}
运行结果：
可以看到，经过多次间隔排序之后，数据已经排好了顺序。 这就是希尔排序，一般的初次取序列的一半为[增量]，以后每次减半，直到增量为1。
最终步骤：
取适合的 增量序列，及最大的间隔。据说 3h+1 ，是最好的。
最终代码：
/**
* 希尔排序
*/
public static void shellSort(){
int[] arr = {49,38,65,97,76,13,27,49,55,4};
int len = arr.length;
int h = 1;
//获取适合的间隔 据说这样取最好
while (h < len/3) h=3*h+1;
while (h>=1){
for (int i = h; i < arr.length; i++) {
for (int j = i; j >= h && arr[j]<arr[j-h]; j-=h) {
swap(arr,j,j-h);
}
}
System.out.println("以间隔为"+h+"进行排序："+Arrays.toString(arr));
h/=3;
}
}
稍微改进一下：
swap() 可以用临时变量替换。
/**
* 希尔排序
*/
public static void shellSort(){
int[] arr = {49,38,65,97,76,13,27,49,55,4};
int len = arr.length;
int h = 1;
//获取适合的间隔 据说这样取最好
while (h < len/3) h=3*h+1;
while (h>=1){
for (int i = h; i < arr.length; i++) {
int tmp=arr[i];
int j = i;
for (; j >= h && tmp<arr[j-h]; j-=h) {
arr[j]=arr[j-h];
}
arr[j]=tmp;
}
System.out.println("以间隔为"+h+"进行排序："+Arrays.toString(arr));
h/=3;
}
}
运行结果：
时间复杂度：
最好情况下：O(n)
最坏情况下：O(n2)
平均时间复杂度：O(n1.3)
空间复杂度：
空间复杂度就是在交换元素时那个临时变量所占的内存空间； 空间复杂度为：O(1)；
稳定性：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
时间性能：
希尔排序在效率上较直接插入排序有较大的改进。
希尔分析：
希尔排序是按照不同步长对元素进行插入排序]，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
