设计两组数据,一组最坏情况,一种一般情况,用快速排序法从大到小排序,数据规模为10000,记录实际运行时间,同时分别分析两种情况运行次数。C语言完整代码
时间: 2024-09-13 20:09:58 浏览: 59
为了回答这个问题,我们需要创建两个数组,一个是随机的整数数组,代表一般情况,另一个是已经部分排序的数组,代表最坏情况。然后我们需要实现快速排序算法,并且使用时间函数记录排序的运行时间。以下是一个简单的C语言代码示例来完成这个任务。
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10000
// 交换两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 快速排序的一个分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 指向比基准小的最后一个元素
for (int j = low; j <= high - 1; j++) {
// 如果当前元素大于或等于基准
if (arr[j] >= pivot) {
i++; // 移动小于基准的元素的边界
swap(&arr[i], &arr[j]); // 交换元素
}
}
swap(&arr[i + 1], &arr[high]); // 将基准元素放到正确的位置
return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是分区索引,arr[pi] 现在在正确的位置
int pi = partition(arr, low, high);
// 分别对分区前后的元素进行递归排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 函数用于填充数组,以便生成最坏情况的输入
void fillWorstCase(int arr[], int size) {
for (int i = 0; i < size; i++) {
arr[i] = size - i; // 逆序排列
}
}
// 主函数
int main() {
int *arrGeneral = (int *)malloc(SIZE * sizeof(int));
int *arrWorst = (int *)malloc(SIZE * sizeof(int));
// 初始化随机数生成器
srand(time(NULL));
// 生成随机数组作为一般情况
for (int i = 0; i < SIZE; i++) {
arrGeneral[i] = rand() % SIZE;
}
// 生成最坏情况数组
fillWorstCase(arrWorst, SIZE);
// 测试一般情况下的排序时间
clock_t start = clock();
quickSort(arrGeneral, 0, SIZE - 1);
clock_t end = clock();
printf("一般情况下的运行时间: %f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
// 测试最坏情况下的排序时间
start = clock();
quickSort(arrWorst, 0, SIZE - 1);
end = clock();
printf("最坏情况下的运行时间: %f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
// 清理动态分配的内存
free(arrGeneral);
free(arrWorst);
return 0;
}
```
请注意,以上代码中的快速排序算法是递归实现的,并且没有进行优化。在最坏情况下(例如输入数组已经排序),快速排序的性能会退化到O(n^2)。为了避免这种情况,可以通过选择随机的pivot或者使用三数取中法等方式来优化算法。
此外,由于不同的系统和编译器可能会影响实际运行时间的测量,因此以上时间仅供参考,并且在不同的环境中可能会有所不同。
阅读全文