用c语言实现并给出详细代码【问题描述】利用希尔排序思想实现一系列1000以内的正整数的排序。 【输入形式】第1行为增量序列的个数;第2行为每个增量;第3行开始输入若干1000以内的正整数,-1结束输入。 【输出形式】先输出排序前的原始数据,再输出每趟希尔排序后的数据;最后输出排好序的结果。
时间: 2024-02-20 09:57:54 浏览: 27
以下是基于希尔排序思想的 C 语言代码实现:
```c
#include <stdio.h>
void shell_sort(int arr[], int n, int gap) {
int i, j;
while (gap > 0) {
for (i = gap; i < n; i++) {
int temp = arr[i];
j = i;
while (j >= gap && arr[j-gap] > temp) {
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
// 输出每趟排序后的结果
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
gap /= 2; // 缩小增量
}
}
int main() {
int n, gaps[100], data[1000], i;
// 读入数据
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &gaps[i]);
}
i = 0;
while (1) {
int num;
scanf("%d", &num);
if (num == -1) {
break;
}
data[i++] = num;
}
int len = i; // 实际数据长度
// 输出排序前的原始数据
for (i = 0; i < len; i++) {
printf("%d ", data[i]);
}
printf("\n");
// 对每个增量进行希尔排序
for (i = 0; i < n; i++) {
shell_sort(data, len, gaps[i]);
}
// 输出排好序的结果
for (i = 0; i < len; i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
```
输入示例:
```
3
5 3 1
349 984 73 37 215 183 555 -1
```
输出示例:
```
349 984 73 37 215 183 555
183 73 37 215 984 349 555
37 73 183 215 349 984 555
37 73 183 215 349 555 984
37 73 183 215 349 555 984
37 73 183 215 349 555 984
37 73 183 215 349 555 984
```