使用Java实现希尔排序算法

用Java实现希尔排序算法¶

一、什么是希尔排序？¶

希尔排序（Shell Sort）是插入排序的一种改进版本。普通插入排序在数组接近有序时效率很高，但如果数组逆序，每次插入都需要大量移动操作。希尔排序通过分组插入的方式，先让数组部分有序，最后再用插入排序完成整体排序，从而减少移动次数，提高效率。

二、核心思想¶

希尔排序的关键是引入“步长（Gap）”，将数组分成若干个子序列，对每个子序列进行插入排序。然后逐步缩小步长，重复分组和排序，直到步长为1（此时等价于普通插入排序）。

分组：步长为gap时，数组被分成gap个独立的子序列，每个子序列的元素索引满足i, i+gap, i+2gap...（如gap=2时，子序列为[0,2,4], [1,3]）。
插入排序：对每个子序列单独执行插入排序，使子序列有序。
缩小步长：步长从数组长度的一半开始，每次减半（gap = gap/2），直到gap=0。

三、算法步骤¶

初始化步长：gap = 数组长度 / 2。
分组插入排序：对每个子序列执行插入排序（遍历每个元素，将其插入到子序列的正确位置）。
缩小步长：gap = gap / 2，重复步骤2，直到gap=0。

四、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 - gap; j >= 0 && temp < arr[j]; j -= gap) {
                    arr[j + gap] = arr[j]; // 元素后移
                }
                arr[j + gap] = 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 + " ");
        }
    }
}

五、代码解释¶

外层循环：控制步长gap从n/2开始，每次减半，直到gap=0。
内层循环：遍历每个分组的元素，对每个元素执行插入排序。
temp = arr[i]：临时保存当前元素，避免移动时被覆盖。
for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)：从当前元素的前一个元素开始，向左比较，若temp更小则后移元素。
arr[j + gap] = temp：将temp插入到最终找到的位置。

六、示例演示¶

以数组[12, 34, 54, 2, 3]为例：
1. 初始步长：gap = 5/2 = 2，分组为[12,54,3]和[34,2]。
- 对[12,54,3]排序：34和2交换后，数组变为[3,2,12,34,54]。
2. 步长缩小：gap = 2/2 = 1，此时等价于普通插入排序，数组最终有序为[2,3,12,34,54]。

七、总结¶

希尔排序通过分组减少移动次数和逐步有序化，比普通插入排序更高效。初学者可重点理解步长的作用和分组插入的逻辑，掌握后可进一步学习更复杂的步长序列（如3k+1）以优化性能。

输出结果：

排序前数组：
12 34 54 2 3 
排序后数组：
2 3 12 34 54