public class ShellSort {
    
    /**
     * 希尔排序（使用 Shell 原始间隔序列）
     */
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // 初始间隔为 n/2，每次减半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                
                // 插入排序，间隔为 gap
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }
    
    /**
     * 希尔排序（使用 Hibbard 间隔序列）
     * Hibbard 序列：1, 3, 7, 15, 31, ...
     * 最坏情况时间复杂度为 O(n^(3/2))
     */
    public static void sortHibbard(int[] arr) {
        int n = arr.length;
        
        // 计算最大的 Hibbard 间隔
        int gap = 1;
        while (gap < n / 3) {
            gap = gap * 3 + 1;  // 1, 4, 13, 40, 121, ...
        }
        
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
            gap = (gap - 1) / 3;
        }
    }
    
    /**
     * 希尔排序（使用 Sedgewick 间隔序列）
     * Sedgewick 序列：1, 5, 19, 41, 109, 209, 505, 929, ...
     * 实际性能通常优于 Hibbard 序列
     */
    public static void sortSedgewick(int[] arr) {
        int n = arr.length;
        
        // Sedgewick 间隔序列
        int[] gaps = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 
                      8929, 16001, 36289, 64769, 146305, 260609};
        
        // 找到最大的可用间隔
        int gapIndex = gaps.length - 1;
        while (gapIndex >= 0 && gaps[gapIndex] >= n) {
            gapIndex--;
        }
        
        while (gapIndex >= 0) {
            int gap = gaps[gapIndex];
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
            gapIndex--;
        }
    }
    
    /**
     * 希尔排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                T key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap].compareTo(key) > 0) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }
}