Go语言数据结构之希尔排序示例详解

希尔排序简介

希尔排序，也称为缩小增量排序，是插入排序的一种更高效的改进版本；希尔排序是非稳定排序算法。

希尔排序的基本思想是已距离进行“减半”的插入排序；先将整个待排序的记录序列分割成若干个子序列，分别进行直接插入排序，待各子序列中的记录基本有序时，再将子序列合并为整体有序序列。

希尔排序的过程

从上面的简介中我们可以得知，希尔排序的主要思路是将待排序的序列分为若干个子序列，然后分别对每个子序列进行插入排序，最终合并起来得到有序序列。

而子序列的数量和长度是如何确定的呢？

在希尔排序中，有一个重要的参数increment，称之为增量，通过这个增量，我们可以将待排序的序列划分为increment个子序列。增量的选取很重要，增量的大小直接影响到排序的效率。

排序的过程可以用下面的示意图表示。

for increment > 0  // 不断缩小增量
  for i = increment; i < len(arr); i++ {  // 对每个子序列进行插入排序
    j = i
    for j >= increment && arr[j-increment] > arr[j] { // 每个子序列的排序操作
      arr[j], arr[j-increment] = arr[j-increment], arr[j]
      j -= increment
    }
  }
  increment = increment / 2 // 增量缩小

示例1：初始序列为[8,5,2,6,9,3,1,4,0,7]，增量为5

我们可以通过对初始序列进行希尔排序，来更好地理解希尔排序。

下面是对上述初始序列进行希尔排序，增量为5的示例。

第一轮排序

初始序列：[8, 5, 2, 6, 9, 3, 1, 4, 0, 7]

第一轮排序后：[3, 0, 1, 4, 2, 5, 7, 6, 9, 8]

第二轮排序

初始序列：[3, 0, 1, 4, 2, 5, 7, 6, 9, 8]

第二轮排序后：[2, 0, 1, 4, 3, 5, 7, 6, 9, 8]

第三轮排序

初始序列：[2, 0, 1, 4, 3, 5, 7, 6, 9, 8]

第三轮排序后：[1, 0, 2, 4, 3, 5, 7, 6, 9, 8]

第四轮排序

初始序列：[1, 0, 2, 4, 3, 5, 7, 6, 9, 8]

第四轮排序后：[0, 1, 2, 4, 3, 5, 7, 6, 9, 8]

第五轮排序

初始序列：[0, 1, 2, 4, 3, 5, 7, 6, 9, 8]

第五轮排序后：[0, 1, 2, 4, 3, 5, 7, 6, 9, 8]

最终得到的有序序列是[0,1,2,3,4,5,6,7,8,9]。

示例2：初始序列为[10, 4, 6, 8, 13, 2, 3], 增量为3

我们再来看一个增量为3的示例。初始序列为[10, 4, 6, 8, 13, 2, 3]。

第一轮排序

初始序列：[10, 4, 6, 8, 13, 2, 3]

第一轮排序后：[3, 4, 6, 8, 13, 2, 10]

第二轮排序

初始序列：[3, 4, 6, 8, 13, 2, 10]

第二轮排序后：[2, 4, 3, 8, 6, 10, 13]

第三轮排序

初始序列：[2, 4, 3, 8, 6, 10, 13]

第三轮排序后：[2, 3, 4, 6, 8, 10, 13]

最终得到的有序序列是[2, 3, 4, 6, 8, 10, 13]。

总结

希尔排序是一种高效的排序算法，通过缩小增量的方式来改进插入排序的效率。希尔排序的核心是增量的选择，增量正确选择可以大大提高排序的效率，增量的选择一般是以序列长度为基础来确定的。

通过初始序列为[8,5,2,6,9,3,1,4,0,7]、[10, 4, 6, 8, 13, 2, 3]的两个示例，我们可以更好地理解希尔排序的基本思路和过程。