希尔排序算法
前面给大家介绍了插入排序算法，通过将待排序序列中的元素逐个插入到有序的子序列中，最终使整个序列变得有序。下图所示的动画演示了插入排序的整个过程：
图 1 插入排序算法
观察动画不难发现，插入排序算法是通过比较元素大小和交换元素存储位置实现排序的，比较大小和移动元素的次数越多，算法的效率就越差。
希尔排序算法又叫缩小增量排序算法，是一种更高效的插入排序算法。和普通的插入排序算法相比，希尔排序算法减少了移动元素和比较元素大小的次数，从而提高了排序效率。
希尔排序算法的实现思路是：
将待排序序列划分成多个子序列，使用普通的插入排序算法对每个子序列进行排序；
按照不同的划分标准，重复执行第一步；
使用普通的插入排序算法对整个序列进行排序。
按照这个思路，我们尝试对 {35, 33, 42, 10, 14, 19, 27, 44} 做升序排序，具体的实现流程是：
- 间隔 4 个元素，将整个序列划分为 4 个子序列：
采用插入排序算法分别对 {35, 14}、{33, 19}、{42, 27}、{10, 44} 进行排序，最终生成的新序列为：
- 间隔 2 个元素，再次划分整个序列：
采用插入排序算法分别对 {14, 27, 35, 42} 和 {19, 10, 33, 44} 进行排序：
- 采用插入排序算法对整个序列进行一次排序，过程如下：
序列的划分方法
待排序序列如何进行划分，划分多少次，都会影响到希尔排序算法的执行效率。
希尔排序算法没有固定的划分标准，这里给大家推荐一种常用的方法，套用如下伪代码：
输入 list //输入待排序序列 interval <- 1 // 初始值为 1 while interval
< length(list) / 3: // length(list) 表示待排序序列的长度
interval = interval * 3 + 1 经过计算得出的 interval 的值，就是首次划分序列采用的标准。后续划分整个序列，套用如下公式： interval = (interval-1)/3
比如说计算第二次划分序列的标准，只需将第一次划分序列时计算得到的 interval 代入公式，求出的新 interval
值就是第二次采用的划分标准。 希尔排序算法的具体实现 实现希尔排序算法的伪代码如下： // 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