#include <iostream>
using namespace std;
// 希尔排序函数
void shellSort(int arr[], int n) {
// 初始增量gap为数组长度的一半，每次循环后减半
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; // 插入正确位置
}
// 输出每一趟排序结果（可选）
cout << "gap = " << gap << " 时的排序结果: ";
for (int k = 0; k < n; k++) {
cout << arr[k] << " ";
}
cout << endl;
}
}
// 打印数组函数
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
// 示例数组
int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "原始数组: ";
printArray(arr, n);
cout << endl;
cout << "希尔排序过程:" << endl;
shellSort(arr, n);
cout << "\n排序后数组: ";
printArray(arr, n);
return 0;
}
( ) |
希尔排序
