随机产生300个整数构成的序列,分别以直接插入、冒泡、希尔、快速、归并等排序算法排序,并统计各自的比较次数。代码怎么写 用c语言写
时间: 2023-12-10 19:37:36 浏览: 26
以下是用C语言实现五种排序算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_NUM 300
void generateRandomSeq(int seq[], int len);
void printSeq(int seq[], int len);
int insertSort(int seq[], int len);
int bubbleSort(int seq[], int len);
int shellSort(int seq[], int len);
int quickSort(int seq[], int left, int right);
int mergeSort(int seq[], int left, int right);
int merge(int seq[], int left, int mid, int right);
int main() {
int seq[MAX_NUM];
int len = MAX_NUM;
// 生成随机序列
generateRandomSeq(seq, len);
// 输出原始序列
printf("Original sequence:\n");
printSeq(seq, len);
// 直接插入排序
int insertComp = insertSort(seq, len);
printf("\nInsertion sort result:\n");
printSeq(seq, len);
printf("Comparisons: %d\n", insertComp);
// 冒泡排序
int bubbleComp = bubbleSort(seq, len);
printf("\nBubble sort result:\n");
printSeq(seq, len);
printf("Comparisons: %d\n", bubbleComp);
// 希尔排序
int shellComp = shellSort(seq, len);
printf("\nShell sort result:\n");
printSeq(seq, len);
printf("Comparisons: %d\n", shellComp);
// 快速排序
int quickComp = quickSort(seq, 0, len - 1);
printf("\nQuick sort result:\n");
printSeq(seq, len);
printf("Comparisons: %d\n", quickComp);
// 归并排序
int mergeComp = mergeSort(seq, 0, len - 1);
printf("\nMerge sort result:\n");
printSeq(seq, len);
printf("Comparisons: %d\n", mergeComp);
return 0;
}
// 生成随机序列
void generateRandomSeq(int seq[], int len) {
srand((unsigned int)time(NULL));
for (int i = 0; i < len; i++) {
seq[i] = rand() % 1000;
}
}
// 输出序列
void printSeq(int seq[], int len) {
for (int i = 0; i < len; i++) {
printf("%d ", seq[i]);
}
printf("\n");
}
// 直接插入排序
int insertSort(int seq[], int len) {
int compCount = 0;
for (int i = 1; i < len; i++) {
int temp = seq[i];
int j = i - 1;
while (j >= 0 && seq[j] > temp) {
seq[j + 1] = seq[j];
j--;
compCount++;
}
seq[j + 1] = temp;
}
return compCount;
}
// 冒泡排序
int bubbleSort(int seq[], int len) {
int compCount = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (seq[j] > seq[j + 1]) {
int temp = seq[j];
seq[j] = seq[j + 1];
seq[j + 1] = temp;
}
compCount++;
}
}
return compCount;
}
// 希尔排序
int shellSort(int seq[], int len) {
int compCount = 0;
int gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
int temp = seq[i];
int j = i - gap;
while (j >= 0 && seq[j] > temp) {
seq[j + gap] = seq[j];
j -= gap;
compCount++;
}
seq[j + gap] = temp;
}
gap /= 2;
}
return compCount;
}
// 快速排序
int quickSort(int seq[], int left, int right) {
int compCount = 0;
if (left < right) {
int pivot = seq[left];
int i = left, j = right;
while (i < j) {
while (i < j && seq[j] >= pivot) {
j--;
compCount++;
}
if (i < j) {
seq[i++] = seq[j];
}
while (i < j && seq[i] < pivot) {
i++;
compCount++;
}
if (i < j) {
seq[j--] = seq[i];
}
}
seq[i] = pivot;
compCount += quickSort(seq, left, i - 1);
compCount += quickSort(seq, i + 1, right);
}
return compCount;
}
// 归并排序
int mergeSort(int seq[], int left, int right) {
int compCount = 0;
if (left < right) {
int mid = left + (right - left) / 2;
compCount += mergeSort(seq, left, mid);
compCount += mergeSort(seq, mid + 1, right);
compCount += merge(seq, left, mid, right);
}
return compCount;
}
int merge(int seq[], int left, int mid, int right) {
int compCount = 0;
int len = right - left + 1;
int* temp = (int*)malloc(len * sizeof(int));
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (seq[i] <= seq[j]) {
temp[k++] = seq[i++];
} else {
temp[k++] = seq[j++];
}
compCount++;
}
while (i <= mid) {
temp[k++] = seq[i++];
compCount++;
}
while (j <= right) {
temp[k++] = seq[j++];
compCount++;
}
for (i = 0; i < len; i++) {
seq[left + i] = temp[i];
}
free(temp);
return compCount;
}
```
这里使用了一个 `generateRandomSeq` 函数来生成随机序列,使用了 `printSeq` 函数来输出序列,每个排序算法的实现都返回比较次数。主函数中分别对五种排序算法进行调用,并输出排序结果和比较次数。