深圳外贸网站建设,手机购物网站怎么推广,公司运营策划方案,电子商务网站建设与管理思考与练习实验任务
(1) 掌握常见比较排序算法的实现#xff1b; (2) 掌握常用比较排序算法的性能及其适用场合。
实验内容
(1) 平均时间复杂度O(n2)和O(nlog2n)的算法至少各选两种实现#xff1b; (2) 待排序的无重复关键字存放在一维整型数组中#xff0c;数量为60000个#xff…实验任务
(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];// ki*21k是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];}
}实验结果
