东莞seo建站公司,江西建设厅官方网站,页游和做网站,网站搭建代理实验1 排序算法的效率分析
一、【实验目的】
#xff08;1#xff09;复习排序算法的实现过程#xff1b;
#xff08;2#xff09;设计平均与最坏情况下时间复杂度的数据环境并理解相关含义#xff1b;
#xff08;3#xff09;初步了解算法时间复杂度的分析方法。…实验1 排序算法的效率分析
一、【实验目的】
1复习排序算法的实现过程
2设计平均与最坏情况下时间复杂度的数据环境并理解相关含义
3初步了解算法时间复杂度的分析方法。
二、【实验内容】
至少选择3种排序算法要求对每种排序算法设计2组数据其中一组为最坏情况一组为一般情况随机数据规模不能少于10000。
记录不同情况下算法的实际运行时间同时分析算法最坏情况与平均情况的运行次数。
三、【实验源代码】
#include stdio.h
#include stdlib.h
#include time.h// 冒泡排序
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]) {// 交换arr[j]和arr[j1]int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}// 快速排序
void quickSort(int arr[], int low, int high);// 快速排序中的分区操作
int partition(int arr[], int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;int temp arr[i];arr[i] arr[j];arr[j] temp;}}int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;
}// 快速排序递归函数
void quickSort(int arr[], int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}// 归并排序中的合并操作
void merge(int arr[], int l, int m, int r) {int n1 m - l 1;int n2 r - m;int L[n1], R[n2];for (int i 0; i n1; i) {L[i] arr[l i];}for (int j 0; j n2; j) {R[j] arr[m 1 j];}int i 0, j 0;int k l;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}while (i n1) {arr[k] L[i];i;k;}while (j n2) {arr[k] R[j];j;k;}
}// 归并排序递归函数
void mergeSort(int arr[], int l, int r) {if (l r) {int m (l r) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}int main() {const int n 10000;int nums[n];srand(time(NULL));for (int i 0; i n; i) {nums[i] rand();}int copy[n];for (int i 0; i n; i) {copy[i] nums[i];}clock_t startTime, endTime;double duration;startTime clock();bubbleSort(copy, n);endTime clock();duration ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf(冒泡排序 %.1f ms\n, duration);for (int i 0; i n; i) {copy[i] nums[i];}startTime clock();mergeSort(copy, 0, n - 1);endTime clock();duration ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf(归并排序 %.1f ms\n, duration);for (int i 0; i n; i) {copy[i] nums[i];}startTime clock();quickSort(copy, 0, n - 1);endTime clock();duration ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf(快速排序 %.1f ms\n, duration);return 0;
}四、实验结果 奇了怪了
