【排序算法】希尔排序

前言：学习希尔排序前最好先掌握插入排序，在进行；不会的可以点击——>【排序算法】插入排序-CSDN博客

一、希尔排序：

        希尔排序，也称为缩小增量排序，是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序在一般用于处理大量数据！！

二、思路：

分成2个阶段：

1、预排序：这个阶段将待排序的数据分成gap组，对每组数据进行插入排序。

2、插入排序：gap==1时，也就是只有1组的情况，这个数组就变成有序数组了。

 具体详情：

1、将一个小于n（元素个数的）的整数作为gap增量，所有距离为gap的元素作为一组数据（也就是我们说的将数组分成gap组）然后对每一组数据进行插入排序，排好后，取一个比第一增量小的整数（比原gap小的组数）重新将新的gap距离的元素作为一组数据