希尔排序 Shell Sort

原理

希尔排序（Shell Sort）是一种基于插入排序的改进排序算法，它通过逐步减少排序的增量（或称间隔）来提升效率。它由计算机科学家 Donald Shell 于 1959 年首次提出，因此得名。

其具体步骤如下：

1. 分组： 将数组按照一定的间隔分成多个子序列，分别对每个子序列进行插入排序。
2. 缩小间隔： 每次排序完成后，将间隔逐步缩小（通常按某种递减序列，例如减半或更复杂的公式），重复对子序列排序。
3. 最终排序： 当间隔缩小到1时，整个数组就成为一个普通的插入排序。

示例

有一组无序数组：

6	2	4	11	9	0	3	1	10	5

取数组长度10的一半并向下取整得到5作为相同序列元素的间隔。

此时有以下几个序列：6 0，2 3，4 1，11 10，9 5。

从前往后对每个序列进行从后往前的插入排序：

1. 6比0大，向后移位，已到达数组尽头，将0插入

2. 3比2大，3原位插入

3. 4比1大，向后移位，已到达数组尽头，将1插入

4. 11比10大，向后移位，已到达数组尽头，将10插入

5. 9比5大，向后移位，已到达数组尽头，将5插入

此时间隔为5的数组排序完成。

取上回间隔5的一半并向下取整得到2作为相同序列元素的间隔。

此时有以下几个序列：0 1 5 3 11，2 10 6 4 9。

从前往后对每个序列进行从后往前的插入排序：

1. 1比0大，1原位插入

2. 10比2大，10原位插入

3. 5比1大，5原位插入

4. 10比6大，向后移位；6比2大，将6插入

5. 5比3大，向后移位；3比1大，将3插入

此时间隔为2的数组排序完成。

取上回间隔2的一半并向下取整得到1作为相同序列元素的间隔。

此时仅剩一个序列：0 2 1 6 3 10 5 4 11 9。

0	2	1	6	4	10	5	4	11	9

从前往后进行从后往前的插入排序：

1. 2比0大，2原位插入

		1	6	3	10	5	4	11	9

2. 2比1大，向后移位；1比0大，将1插入

			6	3	10	5	4	11	9

3. 6比2大，6原位插入

				3	10	5	4	11	9

4. 6比3大，向后移位；3比2大，将3插入

					10	5	4	11	9

5. 10比6大，10原位插入

						5	4	11	9

6. 10比5大，向后移位；6比5大，向后移位；5比3大，将5插入

							4	11	9

7. 10比4大，向后移位；6比4大，向后移位；5比4大，向后移位；4比3大，将4插入

								11	9

8. 11比10大，11原位插入

									9

9. 11比9大，向后移位；10比9大，向后移位；9比6大，将9插入

排序完成。

实现

C++

可视化

数组长度

动画间隔

数组：

[]