希尔排序又称缩小增量排序，是一种比插入排序更高效的排序算法，可以看做是插入排序算法的“改良版”。
希尔排序算法的整个排序过程分为如下几步：
将待排序序列划分为多个子序列，对每个子序列使用插入排序算法进行排序；
依照不同的划分标准，重复执行第 1 步；
最后对整个序列进行一次插入排序操作。
和直接插入排序算法相比，希尔排序算法大大减少了移动元素和比较元素的次数，提高了排序效率。希尔排序算法不仅适用于对规模小的无序数据集进行排序，还适用于中等规模的数据集。
希尔排序算法的基本原理
接下来，我们以对 {35,33,42,10,14,19,27,44} 做升序排序为例，给您演示希尔排序算法的整个执行流程。
1) 首先我们以 4 个元素为间隔，将整个序列划分为多个子序列，如下图所示：
可以看到，我们将整个序列划分为了 {35,14}、{33,19}、{42,27} 和 {10,44} 共 4 个子序列。分别对这 4 个序列做插入排序操作，得到的新序列为：
2) 再以 2 个元素为间隔，划分整个序列，如下图所示：
我们将整个序列划分为了 {14,27,35,42} 和 {19,10,33,44}，分别对它们进行插入排序操作，得到的新序列为：
3) 最后，我们对新序列整体进行一次插入排序操作，排序的过程依次如下图所示：
由此，整个序列成为升序序列，希尔排序完成。
注意，希尔排序的执行效率更多取决于划分标准的制定，比如上面的实例中分别以 4、2、1 作为划分标准。这里给您推荐一种划分方法：
1) 套用如下伪代码，计算出可划分间隔的最大值：
输入 list //输入待排序序列
interval <- 1 // 初始值为 1
while interval < length(list) / 3: // length(list) 表示待排序序列的长度
interval = interval * 3 + 1
最终求得的 interval 即为首次划分序列时采用的标准，即以间隔 interval 个元素划分整个序列。
2) 后续每次以 interval = (interval-1)/3 为标准划分整个序列，直至 interval 的值为 0。
如下为实现希尔排序的伪代码：
// list 为待排序序列
shell_sort(list):
len <- length(list) // 记录 list 序列中的元素个数
//初始化间隔数为 1
interval <- 1
//计算最大间隔数
while interval < len/3:
interval <- interval * 3 + 1
//根据间隔数，不断划分序列，并对各子序列排序
while interval > 0:
//对各个子序列做直接插入排序
for i <- interval to len:
temp <- list[i]
j <- i
while j > interval - 1 && list[j - interval] ≥ temp:
list[j] <- list[j - interval]
j <- j - interval
if j != i:
list[j] <- temp
//计算新的间隔数，继续划分序列
interval <- (interval - 1)/3
return list
希尔排序算法的具体实现
如下是采用希尔排序算法对 {35,33,42,10,14,19,27,44} 进行升序排序的 C 语言程序：
#include <stdio.h>
#define N 8 //设定待排序序列中的元素个数
//list[N] 为存储待排序序列的数组
void shell_sort(int list[N]) {
int temp, i, j;
//初始化间隔数为 1
int interval = 1;
//计算最大间隔
while (interval < N / 3) {
interval = interval * 3 + 1;
}
//根据间隔数，不断划分序列，并对各子序列排序
while (interval > 0) {
//对各个子序列做直接插入排序
for (i = interval; i < N; i++) {
temp = list[i];
j = i;
while (j > interval - 1 && list[j - interval] >= temp) {
list[j] = list[j - interval];
j -= interval;
}
if(j != i){
list[j] = temp;
}
}
//计算新的间隔数，继续划分序列
interval = (interval - 1) / 3;
}
}
int main() {
int i;
int list[N] = { 35,33,42,10,14,19,27,44 };
//对待排序序列做希尔排序
shell_sort(list);
//输出已排序序列
for (i = 0; i < N; i++) {
printf("%d ", list[i]);
}
}
如下是采用希尔排序算法对 {35,33,42,10,14,19,27,44} 进行升序排序的 Java 程序：
public class Demo {
// list[N] 为存储待排序序列的数组
public static void shell_sort(int[] list) {
int length = list.length;
// 初始化间隔数为 1
int interval = 1;
// 计算最大间隔
while (interval < length / 3) {
interval = interval * 3 + 1;
}
// 根据间隔数，不断划分序列，并对各子序列排序
while (interval > 0) {
// 对各个子序列做直接插入排序
for (int i = interval; i < length; i++) {
int temp = list[i];
int j = i;
while (j > interval - 1 && list[j - interval] >= temp) {
list[j] = list[j - interval];
j -= interval;
}
if (j != i) {
list[j] = temp;
}
}
// 计算新的间隔数，继续划分序列
interval = (interval - 1) / 3;
}
}
public static void main(String[] args) {
int[] list = { 35, 33, 42, 10, 14, 19, 27, 44 };
shell_sort(list);
// 输出已排好序的序列
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}
如下是采用希尔排序算法对 {35,33,42,10,14,19,27,44} 进行升序排序的 Python 程序：
格式化复制
#待排序序列 list = [35,33,42,10,14,19,27,44] def shell_sort(): length = len(list) # 初始化间隔数为 1 interval = 1 # 计算最大间隔 while interval < (int)(length / 3): interval = interval * 3 + 1 # 根据间隔数，不断划分序列，并对各子序列排序 while interval > 0: # 对各个子序列做直接插入排序 for i in range(interval , length): temp = list[i] j = i while j > interval - 1 and list[j - interval] >= temp: list[j] = list[j - interval] j = j - interval if j != i: list[j] = temp # 计算新的间隔数，继续划分序列 interval = (int)((interval - 1)/3) # 对待排序序列做希尔排序 shell_sort() # 输出已排好序的序列 for i in list: print(i,end=" ")
以上程序的输出结果均为：
10 14 19 27 33 35 42 44
