C数据结构与算法——常见排序算法时间复杂度比较应用

实验任务

(1) 掌握常见比较排序算法的实现；
(2) 掌握常用比较排序算法的性能及其适用场合。

实验内容

(1) 平均时间复杂度O(n2)和O(nlog2n)的算法至少各选两种实现；
(2) 待排序的无重复关键字存放在一维整型数组中，数量为60000个；
(3) 对于不同的排序算法，分成两轮进行性能对比：
第1轮对比：关键字初始为升序状态；
第2轮对比：关键字初始为乱序状态；

实验源码

// 由于临近期末，所以插入排序和快速排序不加以验证（读者自行验证）#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <profileapi.h>#define LENGTH(arr) (sizeof(arr)/sizeof((arr)[0])) // 计算数组长度void PrintCompare(int arr[], int length); // 打印排序结果
void knuthShuffle(int arr[], int length); // 洗牌算法
void swapInt(int *card_1, int *card_2); // 交换函数
double BubbleSortTimes(int arr[], int length); // 冒泡排序测时
double SelectSortTimes(int arr[], int length); // 选择排序测时
double HeapSortTimes(int arr[], int length); // 堆排序测时
void adjustHeap(int arr[], int i, int length); // 堆排序核心部分(大小堆顶)
double MergeSortTimes(int arr[], int length); // 归并排序测时
void mergeSort(int arr[], int left, int right, int temp[]); // 归分
void merge(int arr[], int left, int mid, int right, int temp[]); // 分治int main() {srand(time(NULL)); // 初始化随机种子printf("======= 排序算法对比 （将 60000 个无重复有序/乱序数据按升序排序）=======\n");printf("\n");printf("------------------- 第01轮比较 初始有序序列排序性能 --------------------\n");int arr[60000];// 有序数组for (int i = 0; i < LENGTH(arr); i++) { // 一副有序牌arr[i] = i + 1;}PrintCompare(arr, LENGTH(arr));printf("\n");printf("------------------- 第02轮比较 初始乱序序列排序性能 --------------------\n");// 无序数组knuthShuffle(arr, LENGTH(arr)); // 洗牌打乱顺序PrintCompare(arr, LENGTH(arr));printf("\n= 测试环境：i7-9750HF @ 4.12Ghz | 16GB RAM | Win 11 X64 | Clion 2022.1 =");getchar();
}void PrintCompare(int arr[], int length) {int tempArr[length];printf("\n ---- 排序算法 ----- - 排序耗时 - ---- 随机展示5个排序后的连续数据 -----\n");printf("【时间复杂度  O(n^2)】\n");for (int i = 0; i < length; i++) {tempArr[i] = arr[i];}printf("  冒泡排序\t\t%7.2lf ms", BubbleSortTimes(tempArr, length));int randIndex = rand() % length; // 0 - (length-1)int printNum = 5;for (int i = 0; i < printNum; i++) {if (tempArr[randIndex] >= (length - printNum)) {i = 0;} else {printf("%7d", tempArr[randIndex++]);}}printf("\n");for (int i = 0; i < length; i++) {tempArr[i] = arr[i];}printf("  直接选择排序\t\t%7.2lf ms", SelectSortTimes(tempArr, length));randIndex = rand() % length; // 0 - (length-1)printNum = 5;for (int i = 0; i < printNum; i++) {if (tempArr[randIndex] >= (length - printNum)) {i = 0;} else {printf("%7d", tempArr[randIndex++]);}}printf("\n");printf("【时间复杂度O(nlogn)】\n");for (int i = 0; i < length; i++) {tempArr[i] = arr[i];}printf("  堆排序\t\t%7.2lf ms", HeapSortTimes(tempArr, length));randIndex = rand() % length; // 0 - (length-1)printNum = 5;for (int i = 0; i < printNum; i++) {if (tempArr[randIndex] >= (length - printNum)) {i = 0;} else {printf("%7d", tempArr[randIndex++]);}}printf("\n");for (int i = 0; i < length; i++) {tempArr[i] = arr[i];}printf("  归并排序\t\t%7.2lf ms", MergeSortTimes(tempArr, length));randIndex = rand() % length; // 0 - (length-1)printNum = 5;for (int i = 0; i < printNum; i++) {if (tempArr[randIndex] >= (length - printNum)) {i = 0;} else {printf("%7d", tempArr[randIndex++]);}}printf("\n");
}void knuthShuffle(int arr[], int length) {for (int i = length - 1; i > 1; i--) {swapInt(&arr[i], &arr[rand() % (i + 1)]);}
}void swapInt(int *card_1, int *card_2) {int tCard;tCard = *card_1;*card_1 = *card_2;*card_2 = tCard;
}double BubbleSortTimes(int arr[], int length) {union _LARGE_INTEGER time_start; // 开始时间union _LARGE_INTEGER time_over; // 结束时间LARGE_INTEGER f; // 计时器频率QueryPerformanceFrequency(&f);double dqFreq = (double) f.QuadPart; // 计时器频率QueryPerformanceCounter(&time_start); // 计时开始int temp;for (int i = 0; i < length - 1; i++) { // 外层循环：轮次int index = -1;for (int j = 0; j < length - 1 - i; j++) { // 内层循环：比较并交换位置(找出每轮最大数)if (arr[j] > arr[j + 1]) {temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;index++;}}if (index == -1) {break; // 为提高排序效率，如果在每轮排序中未发生一次位置交换则代表已经是需要的顺序(直接跳出排序)}}QueryPerformanceCounter(&time_over); // 计时结束// 乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒double run_time = 1000000.0 * (time_over.QuadPart - time_start.QuadPart) / dqFreq;return run_time / 1000.0;
}double SelectSortTimes(int arr[], int length) {struct timespec start;struct timespec end;// 开始时间clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);for (int i = 0; i < length - 1; i++) {int minIndex = i; // 最小数的下标int min = arr[i]; // 最小数的值for (int j = i + 1; j < length; j++) { // 选出本轮最小值，放到当前位置if (min > arr[j]) { // 升序排序min = arr[j];minIndex = j;}}// 将最小值，放在arr[i] (即交换)if (minIndex != i) { // 如果当前位置的数就是最小值，那么不需要进行交换arr[minIndex] = arr[i];arr[i] = min;}}// 结束时间clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);// 总耗时// 转化为 ms 为单位（但是精度可以直接到 ns 级别）double start_ms = start.tv_sec * 1000.0 + start.tv_nsec / 1000000.0;double end_ms = end.tv_sec * 1000.0 + end.tv_nsec / 1000000.0;return end_ms - start_ms;
}double HeapSortTimes(int arr[], int length) {union _LARGE_INTEGER time_start; // 开始时间union _LARGE_INTEGER time_over; // 结束时间LARGE_INTEGER f; // 计时器频率QueryPerformanceFrequency(&f);double dqFreq = (double) f.QuadPart; // 计时器频率QueryPerformanceCounter(&time_start); // 计时开始int temp;// 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆for (int i = length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, length);}for (int i = length - 1; i > 0; i--) {// 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端temp = arr[i];arr[i] = arr[0];arr[0] = temp;// 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序adjustHeap(arr, 0, i); // 从最顶端 下标0 开始重新调整为堆}QueryPerformanceCounter(&time_over); // 计时结束// 乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒double run_time = 1000000.0 * (time_over.QuadPart - time_start.QuadPart) / dqFreq;return run_time / 1000.0;
}void adjustHeap(int arr[], int i, int length) {// 取出当前元素的值，保存为临时变量int temp = arr[i];// k=i*2+1：k是i结点的左子结点for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 在保证有右子结点的前提下，比较左子结点和右子结点的值的大小if (k + 1 < length && arr[k] < arr[k + 1]) {k++; // 如果右子结点大于左子结点，则把 左子结点 赋值为 右子结点}// 如果子结点大于父结点if (arr[k] > temp) {arr[i] = arr[k]; // 把当前子结点的值赋值给父结点i = k; // 把当前子结点作为新的父结点，继续向下循环比较是否还有子结点} else {break; // 直到以 i 父结点的树无子结点未比较为止}}//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)arr[i] = temp; // 将temp值放到调整后的被交换的位置(子结点)
}double MergeSortTimes(int arr[], int length) {union _LARGE_INTEGER time_start; // 开始时间union _LARGE_INTEGER time_over; // 结束时间LARGE_INTEGER f; // 计时器频率QueryPerformanceFrequency(&f);double dqFreq = (double) f.QuadPart; // 计时器频率QueryPerformanceCounter(&time_start); // 计时开始int tempArr[length];mergeSort(arr, 0, length - 1, tempArr);QueryPerformanceCounter(&time_over); // 计时结束// 乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒double run_time = 1000000.0 * (time_over.QuadPart - time_start.QuadPart) / dqFreq;return run_time / 1000.0;
}void mergeSort(int arr[], int left, int right, int temp[]) {if (left < right) {int mid = (left + right) / 2;// 左边分 递归分法mergeSort(arr, left, mid, temp);// 右边分 递归分法mergeSort(arr, mid + 1, right, temp);// 合并法merge(arr, left, mid, right, temp);}
}void merge(int arr[], int left, int mid, int right, int temp[]) {int i = left; // 初始化 i, 左边有序序列的初始索引int j = mid + 1; // 初始化 j, 右边有序序列的初始索引int t = 0; // 指向 temp 数组的当前索引while (i <= mid && j <= right) { // 只要左边或者右边的索引超过if (arr[i] <= arr[j]) { // 左右索引元素开始比较，如果左边小于等// 于右边索引元素值，将小的元素赋值到temp数组中temp[t++] = arr[i++]; // 索引向后 ++ 移动} else {temp[t++] = arr[j++];}}// 如果左边有剩余while (i <= mid) {temp[t++] = arr[i++];}// 如果右边有剩余while (j <= right) {temp[t++] = arr[j++];}t = 0;int tempLeft = left;while (tempLeft <= right) {arr[tempLeft++] = temp[t++];}
}