什么是希尔排序（Shell sort）
希尔排序是插入排序的一种优化算法，先来看百度百科的定义：
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
定义说的严谨，可是吧，一时半会很难看懂。我们知道插入排序是每次都是取基准元素左侧的元素比较大小，也就是每次比较的步长为1，如果是近乎有序的数组，插入排序很容易退化成O（n^2），而希尔排序每次选择的步长是不一样的（当然最后的步长肯定为1，也就是最后用一次插入排序），这是打破插入排序O（n^2）时间复杂度的关键步骤。
所以，希尔排序的思想是：
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
思路分析：
希尔排序是需要先将序列分为若干个子序列，采用什么方法分效率最高，是一个还没有解决的问题，不过，目前希尔排序的分组方法通常采用折半法分组。使用举例方法说明这一点。
假设一个数组arr [3,4,6,7,8,9,1,2,5,0]
则数组长度为len=10，
第一次分组分成5个组，（len/2）
此时需要比较的元素为：
| 组别 | 【下标】元素值 | 【下标】元素值 |
|---|---|---|
| 第一组 | 【0】3 | 【5】9 |
| 第二组 | 【1】4 | 【6】1 |
| 第三组 | 【2】6 | 【7】2 |
| 第四组 | 【3】7 | 【8】5 |
| 第五组 | 【4】8 | 【9】0 |
采用直接插入排序，分组排序结果是：
| 组别 | 【下标】元素值 | 【下标】元素值 |
|---|---|---|
| 第一组 | 【0】3 | 【5】9 |
| 第二组 | 【1】1 | 【6】4 |
| 第三组 | 【2】2 | 【7】6 |
| 第四组 | 【3】5 | 【8】7 |
| 第五组 | 【4】0 | 【9】8 |
比较并交换位置后数组arr变成：
[3，1，2，5，0，9，4，6，7，8]
第二次分组分为 2 个分组，(len/2)/2
| 组别 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 |
|---|---|---|---|---|---|
| 第一组 | 【0】3 | 【2】2 | 【4】0 | 【6】4 | 【8】7 |
| 第二组 | 【1】1 | 【3】5 | 【5】9 | 【7】6 | 【9】8 |
采用直接插入排序对这2个分组进行排序
| 组别 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 | 【下标】元素值 |
|---|---|---|---|---|---|
| 第一组 | 【0】0 | 【2】2 | 【4】3 | 【6】4 | 【8】7 |
| 第二组 | 【1】1 | 【3】5 | 【5】6 | 【7】8 | 【9】9 |
比较和交换位置后数组arr变成：
[0,1,2,5,3,6,4,8,7,9]
第三次分组分为1组，(len/2)/2/2
也就是直接使用插入排序法
[0,1,2,3,4,5,6,7,8,9]
以上就是折半分组法。
Golang代码
/************************************************************
** @Description: shell
** @Author: haodaquan
** @Date: 2018-09-04 22:59
** @Last Modified by: haodaquan
** @Last Modified time: 2018-09-04 22:59
*************************************************************/
package shell
func Sort(arr []int) []int {
len := len(arr)
if len <= 1 {
return arr
}
var i, j, gap int
for gap = len / 2; gap > 0; gap = gap / 2 {
for i = gap; i < len; i++ {
for j = i - gap; j >= 0 && arr[j] > arr[j+gap]; j = j - gap {
arr[j], arr[j+gap] = arr[j+gap], arr[j]
}
}
}
return arr
}
优缺点
希尔排序特别适合近乎有序的序列排序使用
测试代码和性能测试代码已经放到了github上，地址：
https://github.com/george518/PPGo_algorithm/tree/master/sort/shell
不妨一试.
可参考的资料
http://v.youku.com/v_show/id_XNTA3NDUxMjcy.html
http://baidu.iqiyi.com/watch/7194221101908076908.html?page=videoMultiNeed
