点击上方「蓝字」关注我们

上文我们一起学习了解了3种基础的简单排序算法（冒泡算法/简单选择排序算法/快速插入排序算法），这三种算法简单归纳是：

冒泡：通过元素之间的全量比较，达到排序的目的；

简单插入排序算法：通过组合元素为小序列，通过比较将元素插入到特定位置；

快速选择排序：全量比较抽出最大值或最小值，放到数组的开头或者末尾。

以上的算法，在数据量较小且数据大部分有序的情况下，性能可以表现优异；但在生产环境下，面临的往往是杂乱无章且数据量极大的场景，这时候如果继续依赖基础算法，会导致效率低下，或给服务器性能带来较大的压力。所以需要更有效的算法，来帮助我们解决在大数量场景的问题。

下文一起学习下“插入排序”的优化算法 -- “希尔排序”。

背景与基本思想

背景

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

概念

希尔排序也被称为“缩小增量排序”，基本原理是：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个排序序列基本有序后，最后再对所有元素进行一次直接插入排序。

具体步骤如下：

1）选择一个步长序列（t1,t2,···,tk），满足ti > tj(i 0; h = h/2){ // 遍历子序列，每次下标增量为h for (i = h; i < length; i ++){ temp = arr[i]; //待插入元素 // 子序列插入比较。可能会有疑问，为什么不是按照图示的[32,26,60]来逐个比较呢？因为代码不需要像图示那样，额外花销来维护第几趟。 // 当i自增到60的下标时，下面的for循环，相当于会插入比较到[26,32]的子序列里面了。这是非常秒的！ for (j = i-h; j >= 0; j -= h){ if (temp < arr[j]){ //较大值往后挪 arr[j + h] = arr[j]; } else { break; } } // 此时的j