C++怎么实现一个希尔排序_C++排序算法与希尔排序实现

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个希尔排序_C++排序算法与希尔排序实现

2025-11-20

浏览次数：次

返回列表

希尔排序通过分组插入和逐步缩小增量实现高效排序，时间复杂度约O(n^1.3)，优于普通插入排序；其核心思想是用递减的增量序列将数组分组进行插入排序，使元素快速接近最终位置；C++实现中采用gap=n/2开始的递减序列，内层循环对每个子序列插入排序；使用Knuth序列等更优增量可提升性能，算法为原地但不稳定排序。

c++怎么实现一个希尔排序_c++排序算法与希尔排序实现

希尔排序是一种基于插入排序的高效排序算法，它通过将原始数组分成若干个子序列进行插入排序，逐步缩小间隔，最终完成整体排序。相比普通插入排序，希尔排序在处理大规模数据时性能更优，时间复杂度可达到 O(n^1.3) 左右，具体取决于增量序列的选择。

希尔排序的基本思想

希尔排序又叫“缩小增量排序”，它的核心在于：

选择一个增量序列（如 n/2, n/4, ..., 1）
对每个增量 h，将数组中相距 h 的元素组成子序列，并对每个子序列做插入排序
不断减小增量，直到增量为 1，此时再执行一次插入排序，数组即有序

这样做的好处是：前期通过大步长排序让元素快速接近其最终位置，后期用小步长微调，提升整体效率。

C++ 实现希尔排序

下面是一个完整的 C++ 希尔排序实现示例：

#include <iostream>
#include <vector>
<p>void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 初始增量为数组长度的一半
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;
}
}
}</p><p>int main() {
std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
std::cout << "排序前: ";
for (int x : data) std::cout << x << " ";
std::cout << "\n";</p><pre class='brush:php;toolbar:false;'>shellSort(data);

std::cout << "排序后: ";
for (int x : data) std::cout << x << " ";
std::cout << "\n";

return 0;