希尔排序
插入排序的缺点
插入排序虽好，但在有些情况下是有很多缺点的，比如： 14,18,20,36,1,2 除了最后的两个元素，其他的已经有序了，而这两个几乎要移动前面所有的元素。
引出希尔排序
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序的不同之处在于，它会优化比较距离较远的元素。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，所有的元素被分成1组，实际上等同于执行一次插入排序，算法终止。 (就是拆开分组进行排序，排完之后再合并在一起再排序一遍。如下图所示。
希尔排序的基本步骤：
- 选择增量：gap = length / 2,缩小增量：gap = gap /2 ;
- 增加序列：用序列表示增量的选择，{n/2,(n/2)/2,…1}
- 先将整个待排序的序列分割成若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1,t2,…,tk,其中ti>tj,tk = 1; 按增量序列个数k，对整个序列进行k趟排序。 每趟排序，根据对应的增量ti,将待排序分割成若若干长度为m的子序列，分别对各子表进行直接插入排序。
仅增量因子为1时，整个序列作为一个整体来处理， 表长度即为整个序列的长度。
代码实现：
代码语言：javascript复制void ShellSort(int arr[], int len)//希尔排序
{
int gap = len / 2;//增量
for (; gap > 0; gap /= 2)
{
for (int i = gap; i < len; i )
{
int cur = arr[i];
int j = 0;
for (j = i - gap; j >= 0 && arr[j] > cur; j-= gap)
{
arr[j gap] = arr[j];
}
arr[j gap] = cur;
}
}
}
