用c语言实现随机生成一定规模数据,分别用冒泡排序、快速排序、堆排序和归并排序四种排序算法进行排序,记录各排序算法消耗时间,并分析数据规模为多大时,明显与与时间复杂度一致,并写出实验思路和结果
时间: 2024-02-24 12:57:53 浏览: 111
好的,我可以回答你的问题。
首先,为了实现随机生成一定规模的数据,我们可以使用C语言自带的rand()函数来生成随机数,并将其存储到一个数组中。生成数据的代码示例如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void generateData(int data[], int size) {
srand(time(NULL)); // 初始化随机数种子
for (int i = 0; i < size; i++) {
data[i] = rand() % 100; // 生成0~99之间的随机数
}
}
```
接下来,我们可以分别实现冒泡排序、快速排序、堆排序和归并排序算法,并记录它们的执行时间。排序算法的代码示例如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bubbleSort(int data[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
void quickSort(int data[], int left, int right) {
if (left >= right) {
return;
}
int pivot = data[left];
int i = left, j = right;
while (i < j) {
while (i < j && data[j] >= pivot) {
j--;
}
data[i] = data[j];
while (i < j && data[i] <= pivot) {
i++;
}
data[j] = data[i];
}
data[i] = pivot;
quickSort(data, left, i - 1);
quickSort(data, i + 1, right);
}
void heapSort(int data[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(data, size, i);
}
for (int i = size - 1; i >= 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
heapify(data, i, 0);
}
}
void heapify(int data[], int size, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && data[left] > data[largest]) {
largest = left;
}
if (right < size && data[right] > data[largest]) {
largest = right;
}
if (largest != index) {
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
heapify(data, size, largest);
}
}
void mergeSort(int data[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(data, left, mid);
mergeSort(data, mid + 1, right);
merge(data, left, mid, right);
}
void merge(int data[], int left, int mid, int right) {
int size1 = mid - left + 1;
int size2 = right - mid;
int leftArr[size1], rightArr[size2];
for (int i = 0; i < size1; i++) {
leftArr[i] = data[left + i];
}
for (int i = 0; i < size2; i++) {
rightArr[i] = data[mid + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < size1 && j < size2) {
if (leftArr[i] <= rightArr[j]) {
data[k++] = leftArr[i++];
} else {
data[k++] = rightArr[j++];
}
}
while (i < size1) {
data[k++] = leftArr[i++];
}
while (j < size2) {
data[k++] = rightArr[j++];
}
}
```
然后,我们可以通过调用clock()函数来获取排序算法的执行时间,并将其打印出来。执行时间的代码示例如下:
```c
#include <stdio.h>
#include <time.h>
void testSort(int data[], int size) {
int startTime, endTime;
startTime = clock();
bubbleSort(data, size);
endTime = clock();
printf("Bubble Sort: %dms\n", endTime - startTime);
startTime = clock();
quickSort(data, 0, size - 1);
endTime = clock();
printf("Quick Sort: %dms\n", endTime - startTime);
startTime = clock();
heapSort(data, size);
endTime = clock();
printf("Heap Sort: %dms\n", endTime - startTime);
startTime = clock();
mergeSort(data, 0, size - 1);
endTime = clock();
printf("Merge Sort: %dms\n", endTime - startTime);
}
```
最后,我们可以编写一个主函数来测试排序算法的执行时间。主函数的代码示例如下:
```c
#include <stdio.h>
int main() {
int size = 100000;
int data[size];
generateData(data, size);
testSort(data, size);
return 0;
}
```
在这个示例中,我们将数据规模设为了10万。你可以根据自己的需要来修改数据规模。执行程序后,它会依次输出冒泡排序、快速排序、堆排序和归并排序的执行时间。我们可以通过比较它们的执行时间来判断它们的时间复杂度是否一致。
希望这个实验思路和结果对你有所帮助。
阅读全文