希尔排序 java 代码

以下是希尔排序的 Java 代码实现：

public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        int h = 1;
        while (h < n / 3) {
            h = h * 3 + 1; // 计算增量序列
        }
        while (h >= 1) {
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    swap(arr, j, j - h);
                }
            }
            h /= 3; // 缩小增量
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

希尔排序是一种基于插入排序的排序算法，它通过从大到小分别对数据进行插入排序，以缩小数据范围，最终达到排序的目的。该算法的时间复杂度为 O(nlogn)，具有较高的效率。