希尔排序原理与实现

希尔排序是插入排序的优化版本，通过将数组分割为多个子序列进行插入排序，逐步缩小子序列间隔直至完成整体排序。其时间复杂度介于O(n)和O(n²)之间，具体取决于间隔序列的选择。

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }
}

业务数据排序实战

假设需要处理包含商品价格和销量的业务数据，按价格升序排序，价格相同则按销量降序排序：

class Product {
    private String name;
    private double price;
    private int sales;

    // 构造方法和getter/setter省略
}

public class BusinessSort {
    public static void sortProducts(List<Product> products) {
        int n = products.size();
        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                Product temp = products.get(i);
                int j;
                for (j = i; j >= gap && compare(products.get(j - gap), temp) > 0; j -= gap) {
                    products.set(j, products.get(j - gap));
                }
                products.set(j, temp);
            }
        }
    }

    private static int compare(Product a, Product b) {
        if (a.getPrice() != b.getPrice()) {
            return Double.compare(a.getPrice(), b.getPrice());
        }
        return Integer.compare(b.getSales(), a.getSales());
    }
}

性能优化技巧

选择更优的间隔序列可以提升排序效率。Hibbard序列（1, 3, 7, 15...）可将时间复杂度优化至O(n^(3/2))：

public static void hibbardShellSort(int[] arr) {
    int n = arr.length;
    int k = (int)(Math.log(n) / Math.log(2));
    for (int gap = (int)Math.pow(2, k) - 1; gap > 0; gap = (gap - 1)/2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

大数据量处理建议

当处理百万级以上数据时，可结合多线程进行分块希尔排序。将数组分为多个段，分别用不同线程进行希尔排序，最后合并时再进行一次全局希尔排序：

ExecutorService executor = Executors.newFixedThreadPool(4);
List<Future<?>> futures = new ArrayList<>();
int segmentSize = data.length / 4;

for (int i = 0; i < 4; i++) {
    int start = i * segmentSize;
    int end = (i == 3) ? data.length : start + segmentSize;
    futures.add(executor.submit(() -> shellSortSegment(data, start, end)));
}

for (Future<?> future : futures) {
    future.get();
}
shellSort(data); // 全局排序