求各种排序算法的执行时间

求各种排序算法的执行时间
设计一个程序，随机产生n（100，1000，10000，100000，500000，1000000）个1—99的正整数序列，分别采用直接插入排序，折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序算法对其递增排序，求出各种排序算法所需要的绝对时间（毫秒）。

问题

1.输入y或n的时候直接下一行了？

上一次输入后要用 getchar() 清除输入缓冲区中的换行符，否则后续的 scanf 无法正确读取输入
对于字符输入（如选择是否继续的输入），可以使用 scanf(" %c", &continue_flag); 来跳过空白字符，这样就不需要额外的 getchar() 来清除换行符。

2.分配数组时数字太大导致栈溢出？

在堆上动态分配数组，防止栈溢出
int *arr = (int *)malloc(n * sizeof(int));

3.在进行数组排序的时候，需要传入arr的拷贝

需要穿的是深拷贝，浅拷贝会被更改

• memcpy(arr_copy, arr, n * sizeof(int)); // 深拷贝原数组到 arr_copy

4.如何写测量函数运行时长的宏

这是一个语法糖，跟Python中的装饰器类似，我是根据装饰器看c中有无相同语法写的

5.含有递归的排序无法准确测量其运行时间？

需要用另一个函数将其包裹起来，不直接调用这个递归函数

示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <time.h>// 测量函数运行时长的宏
#define TIMER(func, arr, n) \do { \int* arr_copy = (int*)malloc(n * sizeof(int)); \if (arr_copy == NULL) { \printf("内存分配失败！\n"); \return 1;  \} \memcpy(arr_copy, arr, n * sizeof(int));  \clock_t start_time = clock(); \func(arr_copy, n); \clock_t end_time = clock(); \double duration = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000; \printf(#func " running time:   \t%.3f milliseconds.\n", duration); \free(arr_copy); \} while(0)#define MAX_N 1000001  // 最大序列长度// 函数声明
void InsertionSort(int arr[], int n);
void BinInsSort(int arr[], int n);
void ShellSort(int arr[], int n);
void BubbleSort(int arr[], int n);
void QuickSort(int arr[], int n);
void QuickSort_(int arr[], int left, int right);
void SelectionSort(int arr[], int n);
void HeapSort(int arr[], int n);
void Heapify(int arr[], int n, int i);
void MergeSort(int arr[], int n);
void merge(int arr[], int l, int mid, int r);
void mergeSort(int arr[], int l, int r);// 直接插入排序：维护一个有序区，从左到右扫描未排序区，逐个插入到有序区，从右向左确定插入位置
void InsertionSort(int arr[], int n) {// 遍历无序区for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;  // 有序区长度// 遍历有序区，腾出插入位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;  // 插入}
}// 折半插入排序：同直接插入，但使用折半查找法确定插入位置
void BinInsSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];// 二分查找插入位置为 leftint left = 0, right = i - 1;while (left <= right) {int mid = (left + right) / 2;if (arr[mid] < key) {left = mid + 1;} else {right = mid - 1;}}for (int j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}arr[left] = key;}
}// 希尔排序：分组插入排序，先将数组分成若干组，每组内采用直接插入排序，然后逐渐减小组的大小，直到组大小为1
void ShellSort(int arr[], int n) {int gap = n / 2;while (gap > 0) {// i，j 指向分组中的元素for (int i = gap; i < n; i++) {int key = arr[i];int j = i - gap;while (j >= 0 && arr[j] > key) {arr[j + gap] = arr[j];j -= gap;}arr[j + gap] = key;}gap /= 2;}
}// 冒泡排序：两两交换，逐渐减少逆序对数，直到无逆序对
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;}}}
}// 快速排序：分治，选取一个元素作为基准，将小于基准的元素放到左边，反之放右边，递归排序左右两部分
void QuickSort(int arr[], int n) {QuickSort_(arr, 0, n - 1);
}// [left, right]表示需要排序的区域
void QuickSort_(int arr[], int left, int right) {if (left < right) {int pivot = arr[left]; // 选择第一个元素为基准int i = left, j = right;while (i < j) {// 找到右边第一个小于pivot的元素while (arr[i] <= pivot && i < right) {i++;}// 找到左边第一个大于pivot的元素while (arr[j] > pivot) {j--;}// 交换i和j位置的元素if (i < j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 此时left和right都指向中间，基准元素归位arr[left] = arr[j];arr[j] = pivot;// 递归对左右部分进行排序QuickSort_(arr, left, j - 1);QuickSort_(arr, j + 1, right);}
}// 直接选择排序：维护有序区，每一趟从无序区选出最小的元素，放到有序区的末尾
void SelectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int min_index = i;// 遍历无序区for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}if (min_index!= i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}}
}// 堆排序：建立最大堆，从后往前遍历，将最大元素放到堆顶，然后调整堆，使其成为最大堆，重复以上过程，直到堆中只有一个元素
void HeapSort(int arr[], int n) {// 建堆for (int i = n / 2 - 1; i >= 0; i--) {Heapify(arr, n, i);}// 排序for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;Heapify(arr, i, 0);}
}void Heapify(int arr[], int n, int i) {int largest = i;int l = 2 * i + 1;int r = 2 * i + 2;if (l < n && arr[l] > arr[largest]) {largest = l;}if (r < n && arr[r] > arr[largest]) {largest = r;}if (largest!= i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;Heapify(arr, n, largest);}
}// 二路归并排序：分治，先递归分解数组，然后合并排序结果
void MergeSort(int arr[], int n) {mergeSort(arr, 0, n - 1);
}void merge(int arr[], int l, int mid, int r) {int n1 = mid - l + 1;int n2 = r - mid;int *left = (int*)malloc(n1 * sizeof(int));int *right = (int*)malloc(n2 * sizeof(int));for (int i = 0; i < n1; i++) {left[i] = arr[l + i];}for (int i = 0; i < n2; i++) {right[i] = arr[mid + 1 + i];}int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}while (i < n1) {arr[k++] = left[i++];}while (j < n2) {arr[k++] = right[j++];}free(left);free(right);
}void mergeSort(int arr[], int l, int r) {if (l < r) {int mid = l + (r - l) / 2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);}
}int main() {int n;char continue_flag;while (1) {printf("随机生成 n 个1-99之间的正整数序列\n");printf("① 100\n");printf("② 1000\n");printf("③ 10000\n");printf("④ 100000\n");printf("⑤ 500000\n");printf("⑥ 1000000\n");printf("请输入序号选择 n -> ");scanf("%d", &n);// 清除输入缓冲区中的换行符，否则后续的 scanf 无法正确读取输入// getchar();switch (n) {case 1: n = 100; break;case 2: n = 1000; break;case 3: n = 10000; break;case 4: n = 100000; break;case 5: n = 500000; break;case 6: n = 1000000; break;default: printf("输入错误，请重新输入！\n\n"); Sleep(1500);system("cls");continue;  // 继续下一次循环}printf("您选择的序列长度为 %d\n\n", n);/* -------------- 以下为测试代码 -------------- */// 在堆上动态分配数组，防止栈溢出int *arr = (int *)malloc(n * sizeof(int));if (arr == NULL) {printf("内存分配失败！\n");return 1;  // 退出程序，表示内存分配失败}// 使用当前时间作为随机数种子，防止每次运行程序生成相同的随机数序列srand(time(NULL));// 随机生成 n 个 1 到 99 之间的数，并存储到 arr 数组中for (int i = 0; i < n; i++) {arr[i] = (rand() % 99) + 1;  // 生成 1 到 99 之间的随机数}TIMER(InsertionSort, arr, n);TIMER(BinInsSort, arr, n);TIMER(ShellSort, arr, n);TIMER(BubbleSort, arr, n);TIMER(QuickSort, arr, n);TIMER(SelectionSort, arr, n);TIMER(HeapSort, arr, n);TIMER(MergeSort, arr, n);// 释放动态分配的内存free(arr);/* ------------------------------------------- */Sleep(1500);printf("\n是否继续选择？(y/n) -> ");scanf(" %c", &continue_flag);  // 等待 'y' 或 'n' 输入if (continue_flag == 'n') {break;} else {system("cls");}}system("pause");return 0;
}