【算法-希尔】

定义

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

特点

• 时间复杂度: 平均为 O(n log n)，具体取决于所选择的间隔序列。
• 空间复杂度: O(1)，是原地排序。
• 稳定性: 不稳定排序。

算法步骤

1. 将元素分为n列，并对每列进行插入排序。

2. 将n列元素按行进行合并。

3. 重复步骤1-2，其中元素的列数为上次的一半。

代码

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // 初始gap为数组长度的一半，逐步缩小gap
        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];
                }
                // 将temp放在正确的位置
                arr[j] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3,1,6,40};
        shellSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

• 外层循环控制 gap（间隔），初始值为数组长度的一半，每次迭代后将 gap 减半，直到 gap 为 1。
• 内层循环从 gap 位置开始，对每个元素进行插入排序。对于每个 i 位置的元素，在它之前 gap 个位置范围内寻找插入位置，并进行元素的移动。
• 最后将 temp 插入到正确的位置。