杭州网站建设方案服务公司世界工厂网登录

杭州网站建设方案服务公司,世界工厂网登录,广州冼村街道办,电商开源前段时间作者通过一篇文章#xff08;链接地址#xff1a;https://bbs.21ic.com/icview-3451652-1-1.html#xff09;从工作原理#xff0c;算法步骤#xff0c;时间复杂度#xff0c;空间复杂度#xff0c;稳定性#xff0c;源代码和仿真验证等方面介绍了三种常用的排…前段时间作者通过一篇文章链接地址https://bbs.21ic.com/icview-3451652-1-1.html从工作原理算法步骤时间复杂度空间复杂度稳定性源代码和仿真验证等方面介绍了三种常用的排序算法冒泡排序、选择排序、插入排序。其实对于一般的嵌入式系统设计来说这三种排序算法基本上也够用了不过对于更高级的嵌入式系统应用比如航空航天和军事应用等则可能需要更高效的数据排序算法这篇文章作者就带大家一起来看下两个相对来说效率更高的排序算法即归并排序算法和快速排序算法。1、归并排序算法归并排序Merge Sort是一种基于分治法的高效排序算法其核心思想就是将数组递归地分成两半分别排序后再合并成一个有序数组。算法步骤主要包括分解将当前数组从中间分成左右两部分直到子数组长度为1天然有序解决递归地对左右子数组进行归并排序合并将两个已排序的子数组合并成一个有序数组。其中合并是归并排序的核心步骤详细如下初始化一个临时数组用两个指针分别指向左右子数组的起始位置比较指针指向的元素将较小的放入临时数组并移动对应指针重复步骤2直到某一子数组被完全合并将剩余子数组的元素直接追加到临时数组将临时数组拷贝回原数组的对应位置。算法的时间复杂度如下所示最优/最差/平均情况均为 O(nlogn)。每次分解数组需要 O(logn) 层递归每层合并操作需要 O(n) 时间。算法的空间复杂度如下所示O(n)因合并时需要临时数组。算法的主要特点如下所示 稳定排序相等元素的相对顺序不会改变非原地排序需要额外空间但可通过优化减少适合大数据集相比冒泡排序等算法更高效但常数因子较大。C语言实现的算法代码如下复制// 合并两个已排序的子数组voidmerge(intarr[],intleft,intmid,intright) {inti, j, k;intn1 mid - left 1;// 左子数组的大小intn2 right - mid;// 右子数组的大小// 创建临时数组int*L (int*)malloc(n1 *sizeof(int));int*R (int*)malloc(n2 *sizeof(int));// 拷贝数据到临时数组for(i 0; i n1; i)L[i] arr[left i];for(j 0; j n2; j)R[j] arr[mid 1 j];// 合并临时数组回原数组i 0;// 初始化左子数组的索引j 0;// 初始化右子数组的索引k left;// 初始化合并子数组的索引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;}// 释放临时数组内存free(L);free(R);}// 归并排序主函数voidmergeSort(intarr[],intleft,intright) {if(left right) {// 计算中间点避免溢出intmid left (right - left) /2;// 递归排序左半部分mergeSort(arr, left, mid);// 递归排序右半部分mergeSort(arr, mid 1, right);// 合并已排序的两部分merge(arr, left, mid, right);}}在Visual C 6.0软件上验证算法代码的正确性使用硬件板子在Keil软件上测试了排序100个随机数据的算法执行时间排序100个随机数据的算法执行时间tt t2-t1 0.14538978秒 – 0.14512402秒 265.76微秒。2、快速排序算法快速排序Quick Sort是由Tony Hoare 在 1959 年提出的一种高效的分治排序算法其核心思想是通过一趟排序将待排序列分割成独立的两部分其中一部分的所有元素比另一部分小然后递归地对这两部分继续排序。算法步骤主要包括选择基准从数组中选择一个元素作为基准通常选第一个、最后一个或随机元素。分区将小于基准的元素移到基准左侧大于基准的元素移到右侧基准最终位于正确的位置排序后的最终位置递归排序对基准左右两边的子数组重复上述过程直到子数组长度为 1 或 0。时间复杂度平均情况O(n log n)每次分区将数组分成大致相等的两部分递归深度为 log n每层分区操作耗时 O(n)最坏情况O(n²)当数组已有序或逆序时每次分区只能减少一个元素如基准总选到最大/最小值。空间复杂度平均O(log n)最坏O(n)未优化的递归实现。稳定性快速排序是不稳定排序因为分区过程中可能改变相等元素的相对顺序。C语言实现的算法代码如下复制// 交换两个元素的值voidswap(int* a,int* b) {inttemp *a;*a *b;*b temp;}// 分区函数返回基准元素的最终位置intpartition(intarr[],intlow,inthigh) {intpivot arr[high];// 选择最后一个元素作为基准inti (low -1);// i是小于基准的元素的索引for(intj low; j high -1; j) {// 如果当前元素小于或等于基准if(arr[j] pivot) {i;// 增加iswap(arr[i], arr[j]);// 交换元素}}swap(arr[i 1], arr[high]);// 将基准放到正确的位置return(i 1);}// 快速排序主函数voidquickSort(intarr[],intlow,inthigh) {if(low high) {// pi是分区索引arr[pi]现在在正确的位置intpi partition(arr, low, high);// 分别对分区前后的子数组进行排序quickSort(arr, low, pi -1);quickSort(arr, pi 1, high);}}在Visual C 6.0软件上验证算法代码的正确性使用硬件板子在Keil软件上测试了排序100个随机数据的算法执行时间排序100个随机数据的算法执行时间tt t2-t1 0.14519573秒 – 0.14512242秒 73.31微秒。另外快速排序是面试中可能经常会涉及的算法有兴趣的朋友可以深入研究一下从以上对两种排序算法的实测验证可以得出结论在平均情况下快速排序算法的执行速度更快特别是在处理大规模数据的时候归并排序算法的执行时间看上去好像和插入排序算法差不多其实原因是这样的如果测试数据已经是有序的或者接近有序的插入排序会表现得非常好因为它的时间复杂度在最好情况下是O(n)而归并排序的时间复杂度是O(nlogn)在这种特殊情况下归并排序的优势无法体现。因此在实际应用时也要根据待排序数据的有序性和数据量等方面综合考虑选择合适的排序算法甚至可以通过数据排序实测的方法来确定选择使用哪一种排序算法毕竟适合自己的才是最好的加上之前文章介绍的排序算法作者总共提供了五种排序算法供大家参考和选择冒泡排序、插入排序、选择排序、归并排序、快速排序。。---------------------作者dffzh链接https://bbs.21ic.com/forum.php?modviewthreadtid3458580来源21ic.com此文章已获得原创/原创奖标签著作权归21ic所有任何人未经允许禁止转载。