1.定义待排序表的长度为n。2.初始化随机数发生器,产生n个随机数构成的顺序表。3.创建输出排序表函数,取得系统时间函数,直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数.4.主程序调用各个排序函数,输出各排序算法对长度为n的顺序表进行排序所耗费的时间。用c语言写
时间: 2024-02-22 10:00:29 浏览: 57
以下是对应的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000 // 待排序表的长度
// 产生随机数的函数
void generateRandomArray(int *arr, int n) {
srand(time(NULL)); // 初始化随机数发生器
for (int i = 0; i < n; i++) {
arr[i] = rand() % n + 1;
}
}
// 直接插入排序
void insertSort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j;
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
// 冒泡排序
void bubbleSort(int *arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
// 快速排序
int partition(int *arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] > pivot) high--;
arr[low] = arr[high];
while (low < high && arr[low] < pivot) low++;
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
void quickSort(int *arr, int low, int high) {
if (low < high) {
int pivotpos = partition(arr, low, high);
quickSort(arr, low, pivotpos - 1);
quickSort(arr, pivotpos + 1, high);
}
}
// 直接选择排序
void selectSort(int *arr, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
// 筛选排序
void sift(int *arr, int low, int high) {
int i = low, j = 2 * i;
int temp = arr[i];
while (j <= high) {
if (j < high && arr[j] < arr[j+1]) {
j++;
}
if (temp < arr[j]) {
arr[i] = arr[j];
i = j;
j = 2 * i;
} else {
break;
}
}
arr[i] = temp;
}
void heapSort(int *arr, int n) {
for (int i = n/2; i >= 0; i--) {
sift(arr, i, n - 1);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
sift(arr, 0, i - 1);
}
}
// 归并排序
void merge(int *arr, int low, int mid, int high) {
int *temp = (int *)malloc((high - low + 1) * sizeof(int));
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= high) {
temp[k++] = arr[j++];
}
for (int i = 0; i < k; i++) {
arr[low + i] = temp[i];
}
free(temp);
}
void mergeSort(int *arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
// 输出排序表
void outputArray(int *arr, int n, char *sort_name, double time) {
printf("排序算法:%s\n", sort_name);
printf("排序耗时:%lf秒\n", time);
printf("排序结果:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
}
int main() {
int arr[N];
generateRandomArray(arr, N);
clock_t start, end;
double time;
start = clock();
insertSort(arr, N);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "直接插入排序", time);
generateRandomArray(arr, N);
start = clock();
bubbleSort(arr, N);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "冒泡排序", time);
generateRandomArray(arr, N);
start = clock();
quickSort(arr, 0, N - 1);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "快速排序", time);
generateRandomArray(arr, N);
start = clock();
selectSort(arr, N);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "直接选择排序", time);
generateRandomArray(arr, N);
start = clock();
heapSort(arr, N);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "筛选排序", time);
generateRandomArray(arr, N);
start = clock();
mergeSort(arr, 0, N - 1);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC;
outputArray(arr, N, "归并排序", time);
return 0;
}
```
该程序会通过产生随机数进行各种排序算法的测试,并输出排序结果以及排序耗时。
阅读全文