c++怎么实现希尔排序

希尔排序（Shell Sort）是插入排序的一种改进方法。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述如下：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1(i=1,2,…,k)；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。