希尔排序的思想是先对较远的元素进行排序，然后逐渐减小要排序的元素之间的间隔。它是插入排序的通用版本。在希尔排序中，首先对特定间隔的元素进行排序，然后间隔逐渐减小，直至变为1。选择希尔排序的区间的方法有很多种，下面列出其中的几种。请注意，希尔排序的性能取决于所选序列的类型。
- Shell 的原始序列:N/2, N/4, …, 1
- Knuth 序列: 1, 4, 13, …, (3n – 1) / 2
- 塞奇威克数列:1, 8, 23, 77, 281...
- 希巴德数列:1, 3 , 7, 15, 31, 63…
示例:
为了理解希尔排序，让我们考虑一个未排序的数组[10, 1, 23, 50, 4, 9, -4] 并讨论按升序对数组进行排序所采取的每个步骤。在此示例中，考虑了 Shell 的原始序列，因此间隔（间隙）将为三加一(N=7)。
第一遍: 对于此遍，间隙大小为三。因此，将第一个元素 (10) 与第四个元素 (50) 进行比较，并以正确的顺序找到。然后将第二个元素 (1) 与顺序也正确的第五个元素 (4) 进行比较。然后，将第三个元素(23)与第六个元素(9)进行比较，因为(23 > 9)，第六个元素是替换为 (23)，(9) 存储在 temp 变量中。因为，第三项 - 间隙 = 0。因此没有任何元素可以与 temp 进行比较，因此，第三项将被 temp 替换。
之后，将第四个元素(50)与第七个元素(-4)进行比较，因为(50 > -4) ，第七个元素被 (50) 替换，并且 (-4) 存储在 temp 变量中。由于第四个 - 间隙 = 1，因此，temp 再次与第一个元素 (10) 进行比较。由于(10 > -4)，第四个元素被(10)替换，第一个元素被temp替换（没有元素可以与temp进行比较）。
第二遍:对于此遍，间隙大小为一。前四个元素已经排序。之后，将第四个元素(10)与第五个元素(4)进行比较，因为(10 > 4)，第五个元素被 (10) 替换，(4) 存储在 temp 变量中。现在，temp 与大于 temp 的第三个元素 (9) 进行比较，因此第四个元素被 (9 ）。然后，将 temp 与小于 temp 的第二个元素 (1) 进行比较，因此将第三个元素替换为 temp.之后，第六和第七个已排序的元素也会被考虑进行比较。
希尔排序的实现
<?php
//希尔排序函数
function shellsort(&$Array, $n) {
$gap = $n/2;
$gap = (int)$gap;
while($gap > 0) {
for($i = $gap; $i < $n; $i++) {
$temp = $Array[$i];
$j = $i;
while($j >= $gap && $Array[$j-$gap] > $temp) {
$Array[$j] = $Array[$j-$gap];
$j = $j - $gap;
}
$Array[$j] = $temp;
}
$gap = $gap / 2;
$gap = (int)$gap;
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(10, 1, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
shellsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
10 1 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在上述实现中，希尔排序在最坏情况下的时间复杂度为θ(N²)，在最佳和平均情况下的时间复杂度为θ(NlogN)>。有多种方法可以考虑间隙，从而获得更好的时间复杂度。