希尔排序的思想是先对较远的元素进行排序，然后逐渐减小要排序的元素之间的间隔。它是插入排序的通用版本。在希尔排序中，首先对特定间隔的元素进行排序，然后间隔逐渐减小，直至变为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.之后，第六和第七个已排序的元素也会被考虑进行比较。
希尔排序的实现
public class MyClass {
//希尔排序函数
static void shellsort(int Array[]) {
int n = Array.length;
int gap = n/2;
int temp, i, j;
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;
}
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {10, 1, 23, 50, 4, 9, -4};
System.out.println("原始数组");
PrintArray(MyArray);
shellsort(MyArray);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
10 1 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在上述实现中，希尔排序在最坏情况下的时间复杂度为θ(N²)，在最佳和平均情况下的时间复杂度为θ(NlogN)>。有多种方法可以考虑间隙，从而获得更好的时间复杂度。