希尔排序

Posted on Edited on In

题目描述
希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。它通过比较相距一定间隔的元素来进行排序。逐步缩小这个间隔直到为1，最后进行一次普通的插入排序。希尔排序的主要思想是先将整个待排序序列分割成若干个子序列分别进行直接插入排序，待整个序列中的元素”基本有序”时，再对全体元素进行一次直接插入排序。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 10000
-10000 ≤ 数组元素 ≤ 10000

输入样例：

1
2
10
9 8 7 6 5 4 3 2 1 0

输出样例：

1
0 1 2 3 4 5 6 7 8 9

注意事项

  • 希尔排序的时间复杂度取决于增量序列的选择，最坏时间复杂度为 O(n²)，平均时间复杂度约为 O(n^1.3)。
  • 希尔排序的空间复杂度为 O(1)。
  • 希尔排序是不稳定的排序算法。
  • 希尔排序对于中等规模的数组表现较好。

代码实现

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
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

// 希尔排序函数
void shellSort(int a[], int n)
{
    // 选择增量序列：n/2, n/4, ..., 1
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++)
        {
            int temp = a[i]; // 保存当前要插入的元素
            int j = i;
            // 在已排序的子序列中寻找正确的插入位置
            while (j >= gap && a[j - gap] > temp)
            {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp; // 将元素插入到正确的位置
        }
    }
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    shellSort(a, n); // 对整个数组进行希尔排序
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：取决于增量序列的选择，最坏情况下为 O(n²)，平均情况下约为 O(n^1.3)。
  • 空间复杂度：O(1)。

代码解释

  • 希尔排序的核心思想是通过比较相距一定间隔（gap）的元素来进行排序，逐步缩小这个间隔直到为1。
  • 在这个实现中，我们选择的增量序列是 n/2, n/4, …, 1。
  • 对于每个增量 gap，我们将数组分成 gap 个组，每个组内的元素在原数组中间隔 gap 个位置。
  • 然后，我们对每个组内的元素进行插入排序。
  • 随着增量 gap 的逐渐减小，数组会变得越来越有序。
  • 当 gap 减小到 1 时，我们进行一次普通的插入排序，但此时数组已经基本有序，所以插入排序的效率会很高。