希尔排序

1. 前言

本节内容是排序算法系列之一:希尔排序,主要讲解了希尔排序的主体思路,选取了一个待排序的数字列表对希尔排序算法进行了演示,给出了希尔排序算法的 Java 代码实现,帮助大家可以更好的理解希尔排序算法。

2. 什么是希尔排序?

希尔排序(Shell Sort),是计算机科学与技术领域中较为简单的一种排序算法。

希尔排序是插入排序的一种,有时候也被称为 "缩小增量排序"。它是插入排序的改进版,与插入排序的不同之处在于,希尔排序会优先比较距离较远的元素。希尔排序是按照其设计者希尔(Donald Shell)的名字命名而来,并于 1959 年公布出来。

3. 希尔排序过程

在介绍完希尔排序之后,我们一起来看一下希尔排序的实现步骤具体是什么样的吧。这里我们假设待排序的序列为 [9,2,11,7,12,5],我们按照从小到大的序列进行排序。

3.1 算法步骤

1. 步骤 1:

选择一个增量序列 k1,k2, ... km,其中 k1>k2>...km=1,即增量序列大小依次减小,并且最后一个增量序列大小为 1。

2. 步骤 2:

按照增量序列的个数 m,对整个待排序序列进行 m 趟排序。

3. 步骤 3:

每一趟排序,根据对应的增量 ki,需要将待排序的序列分成对应长度的子序列,分别在子序列上面进行直接插入排序。当且仅当增量序列为 1 时,整个序列作为一个整体处理。

其实,上面的步骤 1 和 步骤 2 都是在排序之前进行的处理,选择对应的增量。上面的 步骤 3 每执行一次,就相当于是进行了一次插入排序,只是每次都会选择一个增量,将整个待排序序列按照增量进行划分,然后在对应增量上面进行插入排序。接下来,让我们用上面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照 2.1 节的排序步骤,我们需要先选择对应的希尔排序中的增量值,按照一般性的原则,我们可以将增量按照待排序的序列长度依次整除 2,直到增量为 1 停止,得到对应的增量。如下:

6/2 = 3, 3/2 = 1 //依次获得增量值3,1,除法取整

接着,我们调用 2.1 中的步骤 2, 步骤 3,按照增量值的取法,依次进行对应序列的插入排序,首先我们取增量值为 3,对应排序示例如下:

[9,2,11,7,12,5] --> [9,7],[2,12],[11,5]	 //增量取3,整个待排序序列按照增量为3进行分组,分成3组,依次排序
[9,7],[2,12],[11,5] --> [7,9],[2,12],[5,11] //对应增量位置进行排序
[7,9],[2,12],[5,11] --> [7,2,5,9,12,11] //完成第一次的对应增量的排序过程

Tips: 希尔排序过程中会每次选择一个增量值,然后将待排序列表按照增量值进行分组,对应的分组内部进行插入排序。

在完成增量为 3 的插入排序之后,我们接着进行增量为 1 的插入排序,这个步骤其实跟我们之前的插入排序步骤完全一致。整个过程如下:

[7,2,5,9,12,11] --> [7];[2,5,9,12,11]	 //插入排序初始化,选择第一个元素作为排序好的序列
[7];[2,5,9,12,11] --> [2,7];[5,9,12,11]	 //选择未排序元素2,插入排序好的序列[7]形成新的排序好序列[2,7]
[2,7];[5,9,12,11] --> [2,5,7];[9,12,11]	 //选择未排序元素5,插入排序好的序列[2,7]形成新的排序好序列[2,5,7]
[2,5,7];[9,12,11] --> [2,5,7,9];[12,11]	 //选择未排序元素9,插入排序好的序列[2,5,7]形成新的排序好序列[2,5,7,9]
[2,5,7,9];[12,11] --> [2,5,7,9,12];[11] //选择未排序元素12,插入排序好的序列[2,5,7,9]形成新的排序好序列[2,5,7,9,12]
[2,5,7,9,12];[11] --> [2,5,7,9,11,12] //选择未排序元素11,插入排序好的序列[2,5,7,9,12]形成新的排序好序列[2,5,7,9,11,12]

Tips: 增量为 1 时候执行 步骤 3,实际上就是执行一次插入排序,只是在执行插入排序之前,之前的序列在一定程度上面已经进行了插入排序,所以在增量为 1 的插入排序过程中可以减少插入时候比较的次数,从而可以在一定程度上面减少算法的运行时间。

从上面的示例可以看出,其实整个希尔排序的过程,就是根据增量大小依次进行插入排序,本质上还是针对插入排序的一种优化。

4. Java 代码实现

在说明希尔排序的整个过程之后,接下来,我们看看如何用 Java 代码实现希尔排序算法。

import java.util.Arrays;
public class ShellSort {
 public static void main(String[] args) {
 //初始化需要排序的数组
 int array[] = {9, 2, 11, 7, 12, 5};
 //初始化希尔排序的增量为数组长度
 int gap = array.length;
 //不断地进行插入排序,直至增量为1
 while (true) {
 //增量每次减半
 gap = gap/2;
 for (int i = 0; i < gap; i++) {
 //内部循环是一个插入排序
 for (int j = i + gap; j < array.length; j += gap) {
 int temp = array[j];
 int k = j - gap;
 while (k >= 0 && array[k] > temp) {
 array[k + gap] = array[k];
 k -= gap;
 }
 array[k + gap] = temp;
 }
 }
 //增量为1之后,希尔排序结束,退出循环
 if (gap == 1)
 break;
 }
 //打印出排序好的序列
 System.out.println(Arrays.toString(array));
 }
}

运行结果如下:

[2, 5, 7, 9, 11, 12]

代码中的第 8 行初始化一个需要排序的数组,后面按照从小到大的排序规则,实现了数组的排序。第 12 行至 30 行是整个希尔排序的流程。第 14 行代码表示希尔排序中的增量每次整除 2 取得,第 17 行至 25 行是一个 for 循环结构,表明按照增量进行插入排序。最后第 32 行代码输出排序好的数组。

5. 小结

本节主要学习了希尔排序算法,通过本节课程的学习,需要熟悉希尔排序的算法流程,知道希尔排序算法的实现思路,可以自己用代码实现希尔排序算法。至此,我们已经学习了排序算法中的冒泡排序、插入排序、选择排序、希尔排序。