4.5　希尔排序算法

希尔排序法是插入排序法的一种高级改进版本。希尔排序法可以减少插入排序法中数据移动的次数，加快排序进程，因此又被称为缩小增量排序法。

希尔排序法的基本思想是：将原始数据分成特定间隔的几组数据，然后使用插入排序法对每组数据进行排序，排序后再减小间隔距离，重复插入法对每组数据排序，直到所有数据完成排序为止。

例如，有一组数据：60, 82, 17, 35, 52, 73, 54, 9，如图4.33所示。采用希尔排序算法对其递增排序，步骤如下。

（1）原数列中有8个数据，将间隔数设置为8/2=4位，即每间隔4位的数据为一组，共分为4组，数列1为60, 52，数列2为82, 73，数列3为17, 54，数列4为35, 9，图4.34所示。

（2）将每个数列内的元素按照左小右大的原则进行排序，最后得到的数列1为52, 60，数列2为73, 82，数列3为17, 54，数列4为9, 35。第一次排序结果如图4.35所示。

（3）缩小间隔数为2位，即将原数列间隔2位的数据为一组，共分为两组数列，数列1为52, 17,60, 54，数列2为73, 9, 82, 35，如图4.36所示。

（4）对每个数列内的元素从小到大进行排序，位置错误的元素进行交换，最后得到的数列1为17, 52, 54, 60，数列2为9, 35, 73, 82。第二次排序结果如图4.37所示。

（5）继续缩小间隔数为1位，对图4.37中的元素进行排序，最后的排序结果如图4.38所示。

【实例4.9】　使用希尔排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\09）

用Python代码实现上方示例中的希尔排序算法，具体代码如下：

运行结果如图4.39所示。

【实例4.10】　新闻头条。（实例位置：资源包\Code\04\10）

每天都会有各种各样的新闻发生，点击率较高的新闻就会成为新闻头条。编写程序，利用希尔排序法，根据新闻的点击率对新闻标题进行排序。具体的Python代码如下：

运行结果如图4.40所示。