快速排序c语言要求把数组元素置初始值,个数大约为200000,并互换少量数据,形成大致排好序的序列。按未改进的快速排序算法对A 中元素进行排序,输出快排的计算时间。
时间: 2024-02-11 08:10:03 浏览: 23
以下是基于未改进的快速排序算法对数组进行排序的C语言实现,并计算排序时间:
```c
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void quick_sort(int arr[], int left, int right) {
int i, j, pivot, temp;
if (left < right) {
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i < right) {
i++;
}
while (arr[j] > arr[pivot]) {
j--;
}
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = temp;
quick_sort(arr, left, j - 1);
quick_sort(arr, j + 1, right);
}
}
int main() {
int n = 200000;
int arr[n];
srand((unsigned)time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000;
}
clock_t start_time = clock();
quick_sort(arr, 0, n - 1);
clock_t end_time = clock();
double time_used = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
printf("快速排序计算时间为:%.6f秒\n", time_used);
return 0;
}
```
在这个程序中,我们使用了`time.h`库中的`clock()`函数计算程序运行时间,使用了`stdlib.h`库中的`rand()`函数生成随机数,以便生成初始的乱序数组。在运行程序时,它会生成一个长度为200000的随机数组并对其进行排序,输出排序时间。
需要注意的是,由于快速排序的时间复杂度取决于数组的初始状态,因此排序的计算时间会有所不同,这里给出的时间仅供参考。