希尔排序学习笔记
介绍
希尔排序是一种基于插入排序的排序算法，由Donald Shell在1959年提出。希尔排序通过比较间隔为h的元素来进行排序，通常将数组按升序排序。该算法的时间复杂度约为O(n^(3/2))，但实际效率通常比其他O(n^(3/2))的算法要高。
算法步骤
希尔排序的基本思想是将待排序的数组分割成若干个子序列，然后对每个子序列进行插入排序，最后整个序列就是有序的了。
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
示例
假设数组arr = [70, 80, 50, 30, 60, 20]，使用希尔排序进行排序。
第一轮增量为n/2=3，子序列为：
Copy Code[70, 30]
[80, 60]
[50, 20]
对每个子序列进行插入排序，得到：
Copy Code[30, 70]
[60, 80]
[20, 50]
将子序列合并，得到：[30, 60, 20, 70, 80, 50]
第二轮增量为1，子序列为：
Copy Code[30, 60, 20, 70, 80, 50]
对子序列进行插入排序，得到：[20, 30, 50, 60, 70, 80]
最终，数组arr被排序为[20, 30, 50, 60, 70, 80]。
总结
希尔排序是一种高效的排序算法，在实际应用中广泛使用。希尔排序通过不断地缩小增量来进行排序，比传统的插入排序具有更高的效率。