Java希尔排序

希尔排序是一种改进的插入排序算法，也称为缩小增量排序。它通过将待排序的数组按照一定的间隔分割成若干个子序列，然后对这些子序列进行插入排序，随着排序进行，逐渐减小间隔，直至间隔为1，最后对整个数组进行一次插入排序。这样做的好处是，在初始阶段，子序列中的元素较少，插入排序的代价较小，而且数组中的元素已经基本有序，这样一来，后续的插入排序效率就会提高。

希尔排序的步骤如下：

1. 选择一个增量序列，一般选择增量序列为n/2, n/4 , … , 1，其中n为数组的长度。
2. 按照增量序列对数组进行分组，分成若干个子序列。
3. 对每个子序列进行插入排序。
4. 缩小增量，重复步骤2和3，直至增量为1。

下面是用Java实现的希尔排序示例代码：

public class ShellSort {

    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始增量设定为数组长度的一半，依次递减, 这里的 /2 可以用 >>1 替代,性能更佳
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 插入排序
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 1, 3, 2, 6, 8, 7, 9};
        System.out.println("排序前数组：" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后数组：" + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27