SCAU8640--希尔排序

8640 希尔(shell)排序

时间限制:1000MS  代码长度限制:10KB
提交次数:1858 通过次数:1304

题型: 编程题   语言: G++;GCC

Description

用函数实现希尔(shell)排序，并输出每趟排序的结果,初始增量d=n/2,其后d=d/2

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

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

#include <iostream>
#include <vector>
using namespace std;

// 希尔排序函数
void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 初始增量为 n / 2，每趟减半
    for (int d = n / 2; d > 0; d /= 2) {
        // 对每个步长d进行插入排序
        for (int i = d; i < n; ++i) {
            int key = arr[i];
            int j = i;
            // 对 d 间隔的子序列做插入排序
            while (j >= d && arr[j - d] > key) {
                arr[j] = arr[j - d];
                j -= d;
            }
            arr[j] = key;
        }

        // 输出当前排序结果
        for (int i = 0; i < n; ++i) {
            cout << arr[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);

    // 输入数据
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // 执行希尔排序
    shellSort(arr);

    return 0;
}

希尔排序（Shell Sort）是插入排序的一种改进版本，由 Donald Shell 在 1959 年提出。它主要是为了克服普通插入排序在数据量大时效率低的问题，通过分组让数据更快地接近有序。

🧠 原理简介：

希尔排序的核心思想是：

先将整个待排序的序列按某个“步长（gap）”分成若干组，对每组分别进行插入排序。随后逐渐减小步长，再次进行分组插入排序，最终步长减小到 1 时，整个序列已经基本有序，再做一次插入排序就可以很快完成。

🔁 步骤演示（假设 n=10）：

输入序列：

5 4 8 0 9 3 2 6 7 1

1. 第一轮：gap = n / 2 = 5
   分成 5 组进行插入排序：

   • 第1组: 5 3

   • 第2组: 4 2

   • 第3组: 8 6

   • 第4组: 0 7

   • 第5组: 9 1
     排完得到（示例）：

   3 2 6 0 1 5 4 8 7 9
   

2. 第二轮：gap = 2
   对间隔为 2 的元素进行插入排序

3. 第三轮：gap = 1（即普通插入排序）
   数组已经基本有序，这一步非常快。