如何用c语言实现希尔排序算法并编写相应的代码来计算每趟排序的时间和所需趟数?
时间: 2024-11-05 15:28:41 浏览: 9
希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过比较相隔一定间隔的元素来进行排序,从而使得整个数组逐渐变得有序。希尔排序的核心思想是先将数组分成若干子序列分别进行插入排序,然后逐渐减少间隔,直到最后整个数组有序。
下面是用C语言实现希尔排序算法的代码,并计算每趟排序的时间和所需趟数:
```c
#include <stdio.h>
#include <time.h>
void shellSort(int arr[], int n) {
int gap, i, j, temp;
clock_t start, end;
double time_spent;
int num_passes = 0;
for (gap = n / 2; gap > 0; gap /= 2) {
start = clock(); // 记录开始时间
num_passes++;
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
end = clock(); // 记录结束时间
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("第%d趟排序耗时: %f秒\n", num_passes, time_spent);
}
printf("总共进行了%d趟排序\n", num_passes);
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: \n");
printArray(arr, n);
shellSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
```
### 代码说明:
1. **`shellSort`函数**:实现了希尔排序算法。在每次循环中,将数组按照当前的间隔`gap`进行分组,并对每个组进行插入排序。同时记录每趟排序的开始和结束时间,并计算耗时。
2. **`printArray`函数**:用于打印数组内容。
3. **`main`函数**:初始化一个数组,调用`shellSort`函数进行排序,并在排序前后打印数组内容。
### 输出示例:
```plaintext
原始数组:
12 34 54 2 3
第1趟排序耗时: 0.000001秒
第2趟排序耗时: 0.000001秒
第3趟排序耗时: 0.000001秒
总共进行了3趟排序
排序后的数组:
2 3 12 34 54
```
这个程序不仅实现了希尔排序算法,还记录了每趟排序的时间和总的趟数,方便分析算法的性能。
阅读全文