此博客用于个人学习，来源于算法的书籍和网上的资料，对知识点进行一个整理。
1. 概述：
希尔排序是一种基于插入排序的快速的排序算法，对于大规模乱序数组插入排序很慢，因为它之后交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另外一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
2. 算法：
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的，这样的数组被称为 h 有序数组。在进行排序的时候，如果 h 很大，我们就能将元素移动到很远的地方，为实现更好的 h 有序创造方便。我们这里使用的是 N/3 开始递减到 1 的递增序列。sort 方法的大体逻辑与插入排序相同，但在外面加入一层 while 循环，循环变量 h 每次除以三，与前面对应。
3. 代码实现：
public class Shell {
public static void sort(Comparable
[] a
){
int h
= 1;
while (h
< a
.length
/3){
h
= h
*3 + 1;
}
while (h
>= 1){
for (int i
= 0;i
< a
.length
;i
++){
for (int j
= i
;j
> 0 && less(a
[j
],a
[j
-h
]);j
-= h
){
exchange(a
,j
,j
-h
);
}
}
h
/= 3;
}
}
private static boolean less(Comparable v
,Comparable w
){
return v
.compareTo(w
) < 0;
}
private static void exchange(Comparable
[] a
,int i
,int j
){
Comparable t
= a
[i
];
a
[i
] = a
[j
];
a
[j
] = t
;
}
private static void show(Comparable
[] a
){
for (int i
= 0;i
< a
.length
;i
++){
System
.out
.println(a
[i
]+" ");
}
System
.out
.println();
}
public static boolean isSorted(Comparable
[] a
){
for (int i
= 1;i
< a
.length
;i
++){
if (less(a
[i
],a
[i
-1])){
return false;
}
}
return true;
}
}
4. 特点：
希尔排序是一种在实际应用中都十分常见的算法，因为对于中等大小的数组它的运行时间是可以接受的，它的代码量很小，而且不需要使用额外的内存空间。更加高效的算法确实也有，但他们可能只会比希尔排序快两倍（甚至可能还不到），而且更加复杂。如果你需要解决一个排序问题而又没有系统排序函数可以用，可以先用希尔排序，然后再考虑是否值得将它替换成更加复杂的排序算法。
5. 算法分析：
时间复杂度：希尔排序的复杂度和增量序列是相关的，但在最坏情况下（数组逆序），复杂度为 O(n^2)。空间复杂度：只是用了2个循环变量以及1到2个标志和交换等的中间变量，这个与待排序的记录个数无关，空间复杂度为 O(1)。稳定性：不稳定的，虽然插入排序是稳定的，但是希尔排序在插入的时候是跳跃性插入的，有可能破坏稳定性。例如 7 5 5 8，当 i = 2时，分成两组 [7 5]，[5 8]。分别使用插入排序后，第一组为 [5 7]，第二组为 [5 8]。 合并后可以发现，两个 5（相同元素）的相对位置发生了改变。
