排序算法-希尔排序

前言：排序是现在程序员的必备技能，是很多公司的面试必考点，不管是做移动端，后端开发，排序是绕不过的，众生平等。学习其排序的思想往往能解决不同类型的问题，所以静下心来，研究一下不同的排序算法，算是对自己有一个提升。

排序概述：排序就是将一组对象按照某种逻辑顺序重新排列的过程。

十大排序算法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序，希尔排序，计数排序，基数排序，桶排序。

本文对希尔排序走一个解析：

希尔排序步骤：

1.一种基于插入排序的快速排序算法。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点得从数组一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。

2.希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法突破0(n^2)的第一批算法之一。

3.希尔排序是把待排序数组按一定数量的分组，对每组使用直接插入排序算法排序；然后缩小数量继续分组排序，随着数量逐渐减少，每组包含的元素越来越多，当数量减至1时，整个数组恰被分成一组，排序就完成了。这个不断缩小的数量，就构成了一个增量序列。

代码举例：

对一个数组进行排序：（86,11,77,23,32,45,58,63,93,4,37,22）

int[] array = {86,11,77,23,32,45,58,63,93,4,37,22};

排序代码展示： 

希尔排序

调用sort方法后打印如下：

希尔排序打印

对该案例进行分析：（86,11,77,23,32,45,58,63,93,4,37,22）

(1)  当gap = 6，因为该数组长度为12，那么就从58开始 到22这一组， 根据排序代码所知：currentValue = 58（待排序元素）preIndex = 0   currentValue < 第0个位置也就是86。 满足while条件进入：58这个位置变成了86  第0个位置就变成了58.直至for循环结束，完成了第一组排序。

         数组变成 ------》 [58, 11, 77, 4, 32, 22, 86, 63, 93, 23, 37, 45] 

(2)当gap = 3,因为该数组长度为12.  那么就从4开始 到45这一组依然按照第(1)顺序进行操作。

         数组变成 ------》 [4, 11, 22, 23, 32, 45, 58, 37, 77, 86, 63, 93]

(3)当gap = 1,因为该数组长度为12.  那么就从11开始 到93这一组依然按照第(1)顺序进行操作。

         数组变成 ------》 [4, 11, 22, 23, 32, 37, 45, 58, 63, 77, 86, 93]

至此排序结束

 打印每个步骤的数组：

步骤打印

 至此希尔排序就到这里讲解结束了，细看的话其实一点也不复杂。