希尔排序(Shell's Sort)是插入排序的一种是直接插入排序算法的一种更高效的改进版本，又称“缩小增量排序”。希尔排序是非稳定排序算法。
1. 算法描述
- 先取一个小于待排序数列长度n的整数d1作为第一个增量，将所有距离为d1的倍数的记录放在同一个组中。（一般的初次取序列的一半为增量，以后每次减半，直到增量为1。）
- 在各组内进行插入排序；
- 然后，取第二个增量d2<d1重复上述的分组和排序，直至增量为1，即所有记录放在同一组中进行插入排序。
希尔排序比插入排序高效是因为：希尔排序是比较相隔较远距离（增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。
2. 动图演示
image
3. 代码实现
function shell_sort2($arr) {
if(!is_array($arr)) return;
$len = count($arr);
/**
* $gap为增量，用向右移1位的方式，得到初次增量为序列的一半
* 并且增量每次减半，直到增量为1
*/
for ($gap = $len >> 1; $gap > 0; $gap = $gap >> 1) {
/**
* $i为增量数，同时也是分组数，遍历分组，对每个组中的记录数进行插入排序
*/
for($i = $gap; $i < $len; $i++) {
/**
* 遍历每个组中的记录，比较间隔为增量的两个数，如果后者大于前者则交换两者位置
* 下面的插入排序可类比后面的插入排序算法
*/
for($j = $i - $gap; $j >= 0 && $arr[$j + $gap] < $arr[$j]; $j -= $gap) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + $gap];
$arr[$j + $gap] = $temp;
}
/*
$preIndex = $i - $gap;
$current = $arr[$i];
while ($preIndex >= 0 && $current < $arr[$preIndex]) {
$temp = $arr[$preIndex];
$arr[$preIndex] = $arr[$preIndex + $gap];
$arr[$preIndex + $gap] = $temp;
$preIndex -= $gap;
}
*/
}
}
return $arr;
}
