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（即普通插入排序）
   数组已经基本有序，这一步非常快。