随机产生300个整树构成的序列,分别以直接插入、冒泡、希尔、快速、归并等排序算法排序,并统计各自的比较次数,用c语言实现
时间: 2023-08-16 09:06:25 浏览: 51
以下是使用C语言实现上述要求的代码。其中,生成随机整数序列的函数为rand(),排序算法使用了直接插入排序、冒泡排序、希尔排序、快速排序和归并排序。
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_NUM 300
// 生成随机数序列
void generate_random_sequence(int *arr, int len)
{
srand((unsigned)time(NULL));
for (int i = 0; i < len; i++) {
arr[i] = rand() % 1000; // 生成0~999的随机整数
}
}
// 直接插入排序
int direct_insertion_sort(int *arr, int len)
{
int cmp_count = 0;
for (int i = 1; i < len; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > tmp) {
cmp_count++;
arr[j + 1] = arr[j];
j--;
}
cmp_count++;
arr[j + 1] = tmp;
}
return cmp_count;
}
// 冒泡排序
int bubble_sort(int *arr, int len)
{
int cmp_count = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
cmp_count++;
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return cmp_count;
}
// 希尔排序
int shell_sort(int *arr, int len)
{
int cmp_count = 0;
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
int tmp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
cmp_count++;
arr[j] = arr[j - gap];
}
cmp_count++;
arr[j] = tmp;
}
}
return cmp_count;
}
// 快速排序
void quick_sort(int *arr, int left, int right, int *cmp_count)
{
if (left >= right) {
return;
}
int i = left, j = right;
int pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
(*cmp_count)++;
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
(*cmp_count)++;
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
quick_sort(arr, left, i - 1, cmp_count);
quick_sort(arr, i + 1, right, cmp_count);
}
// 归并排序
void merge(int *arr, int left, int mid, int right, int *cmp_count)
{
int len1 = mid - left + 1;
int len2 = right - mid;
int *L = (int*)malloc(len1 * sizeof(int));
int *R = (int*)malloc(len2 * sizeof(int));
for (int i = 0; i < len1; i++) {
L[i] = arr[left + i];
}
for (int i = 0; i < len2; i++) {
R[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
(*cmp_count)++;
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < len1) {
arr[k++] = L[i++];
}
while (j < len2) {
arr[k++] = R[j++];
}
free(L);
free(R);
}
void merge_sort(int *arr, int left, int right, int *cmp_count)
{
if (left >= right) {
return;
}
int mid = (left + right) / 2;
merge_sort(arr, left, mid, cmp_count);
merge_sort(arr, mid + 1, right, cmp_count);
merge(arr, left, mid, right, cmp_count);
}
int main()
{
int arr[MAX_NUM];
int len = MAX_NUM;
generate_random_sequence(arr, len);
int cmp_count;
// 直接插入排序
cmp_count = direct_insertion_sort(arr, len);
printf("直接插入排序比较次数: %d\n", cmp_count);
// 冒泡排序
generate_random_sequence(arr, len); // 重新生成随机数序列
cmp_count = bubble_sort(arr, len);
printf("冒泡排序比较次数: %d\n", cmp_count);
// 希尔排序
generate_random_sequence(arr, len);
cmp_count = shell_sort(arr, len);
printf("希尔排序比较次数: %d\n", cmp_count);
// 快速排序
generate_random_sequence(arr, len);
cmp_count = 0;
quick_sort(arr, 0, len - 1, &cmp_count);
printf("快速排序比较次数: %d\n", cmp_count);
// 归并排序
generate_random_sequence(arr, len);
cmp_count = 0;
merge_sort(arr, 0, len - 1, &cmp_count);
printf("归并排序比较次数: %d\n", cmp_count);
return 0;
}
```