希尔排序java代码

希尔排序是一种高效的不稳定排序算法，它是插入排序的改进版本。希尔排序通过将数组分成多个子序列来进行排序，然后逐步缩小子序列的间隔，最终将整个数组排序。

java
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;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        
        System.out.println("原始数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        shellSort(arr);

        System.out.println("\n排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

上述代码定义了一个 shellSort 方法，用于对整数数组进行希尔排序。在 main 方法中，我们可以看到如何使用这个排序算法对一个数组进行排序。希尔排序的核心思想是通过逐步缩小间隔，使得元素能够更快地移动到它们最终的位置，从而提高了排序的效率。

首先，我们初始化一个间隔为数组长度的一半，然后在每次迭代中将间隔减半。

在每个间隔下，我们执行插入排序。插入排序的思想是将当前元素插入到已排序的子数组中的合适位置。

在内部插入排序中，我们从数组的第 gap 个元素开始，然后将其与之前间隔 gap 的元素比较，如果前面的元素较大，就将它们交换位置，直到找到合适的插入位置。

重复上述步骤，直到 gap 为 1，此时整个数组将被排序。

希尔排序的时间复杂度取决于间隔序列的选择，最坏情况下为 O(n^2)，但通常情况下表现得相当快，比插入排序和选择排序要快得多。希尔排序是一种原地排序算法，适用于中等大小的数据集。