如何进行希尔排序？

Nen 2021-10-09 16:14

- 程序员

希尔排序也称为“缩小增量排序”，它的基本原理如下：首先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，最后再对所有元素进行一次直接插入排序。

具体步骤如下：选择一个步长序列t1，t2，…，tk，满足ti>tj(i<j)，tk=1。

按步长序列个数k，对待排序序列进行k趟排序。每趟排序，根据对应的步长ti，将待排序列分割成ti个子序列，分别对各个子序列进行直接插入排序。

注意，当步长因子为1时，所有元素作为一个序列来处理，其长度为n。以数组{26， 53， 67， 48， 57， 13， 48， 32， 60， 50}，步长序列为{5， 3， 1}为例。具体步骤如下：

程序示例如下：

程序输出为：

0 1 2 3 4 5 6 7 8 9

希尔排序的关键并不是随便地分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式地移动，使得排序的效率提高。