希尔排序

算法思路

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组。所有距离为的记录分在同一组内，并对每一组内的记录进行直接插入排序。然后，取重复上述分组和排序的工作。当到达=1 时，所有记录在统一组内排好序。

图解

Shell_sort.png

算法特性

希尔排序的特性总结：
希尔排序是对直接插入排序的优化。直接插入排序的特定就是数据越有序，速度越快。

当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

时间复杂度：
希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定： 有学者通过大量的试验统计，得出结果为：O(n1.25) - O(1.6*n1.25)

空间复杂度：O(1)

稳定性：
不相邻的元素也会进行位置交换，是不稳定。

算法实现

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>

// 希尔排序函数
void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    // 初始化间隔序列，这里采用Hibbard间隔序列
    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;
        }
    }
}

int main() {
    std::vector<int> arr = { 12, 34, 54, 2, 3, 14, 56, 23, 11, 9 };
    std::cout << "Before sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    shellSort(arr);

    std::cout << "After sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def shell_sort(arr):
    n = len(arr)
    # 初始化间隔序列，这里采用经典的Hibbard间隔序列，初始间隔为数组长度的一半
    gap = n // 2
    # 只要间隔大于 0，就继续进行排序
    while gap > 0:
        # 对每个间隔进行插入排序
        for i in range(gap, n):
            # 暂存当前要比较和插入的元素
            temp = arr[i]
            j = i
            # 按照当前间隔进行比较和移动元素，将较小的元素往前移动
            while j >= gap and arr[j - gap] > temp:
                # 将较大的元素往后移动
                arr[j] = arr[j - gap]
                j -= gap
            # 将暂存的元素插入到合适的位置
            arr[j] = temp
        # 缩小间隔，准备下一轮排序
        gap //= 2
    return arr

# 测试示例
arr = [12, 34, 54, 2, 3, 14, 56, 23, 11, 9]
print("Before sorting:", arr)
sorted_arr = shell_sort(arr)
print("After sorting:", sorted_arr)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class ShellSort {
    // 希尔排序方法
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始化间隔序列，采用经典的Hibbard间隔序列，初始间隔为数组长度的一半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个间隔进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];  // 暂存当前要插入的元素
                int j = i;
                // 按照当前间隔进行比较和移动元素，将较小的元素往前移动
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];  // 将较大的元素往后移动
                    j -= gap;
                }
                arr[j] = temp;  // 将暂存的元素插入到合适的位置
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3, 14, 56, 23, 11, 9};
        System.out.print("Before sorting: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        shellSort(arr);

        System.out.print("After sorting: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}