编辑
哈喽大家好,我是保护小周ღ,本期为大家带来的是常见排序算法中的归并排序,博主在这里先分享归并排序的递归算法,包您一看就会,快来试试吧~
编辑
编辑
目录
一、归并排序
1.1 基本思想
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序 列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
1.2 算法思想
编辑
到这里,我们可以得到一条结论,两个有序的子序列可以合成一个新的有序子序列,通过递归,我们两个新的有序序列也可以组成新的有序数列,最终实现排序的目的。有些朋友就会问了,这个我懂,关键是咋实现有序数列,其实非常的简单,分割递归至每个子序列只有一个元素时,是不是就有序啦,然后就可以合成有两个元素有序的列表嘛,再合成4个,8个……
编辑
1.3 程序设计思想
定义一个tmp数组,可以是动态开辟的(malloc),用于临时存放合并后的有序数据,定义_MergeSort()函数,用于分解,合并数据(递归实现),参数有,待处理数组,数据区间(数组下标),tmp数组。
- 判断区间是否存在,区间不存在以及只有一个元素的情况结束程序。
- 分割区间:mid=(left+right)/2;递归左右区间,分割递归至每个子序列只有一个元素。
- 每两个子序列一组,循环遍历每一个元素,if比较两个子序列各元素的大小,取大或取小,放入tmp数组,tmp[index++]=子序列++;直到有一个子序列遍历完,循环结束。
- 循环判断是子序列是否遍历完毕,未遍历完毕的子序列剩余元素直接给到tmp数组。
- 将tmp数组的对应的元素拷贝回原数组(已有序)。
1.4 程序实现
//动态开辟空间的函数的头文件void_MergeSort(int*a,intleft,intright,int*tmp) { //区间不存在以及只有一个元素的情况结束程序if (left>=right) { return; } intmid= (left+right) /2; //假设[left,mid],[mid+1,right]有序,那么我们就可以归并了//递归使左右区间有序//分割递归至每个子序列只有一个元素_MergeSort(a,left,mid,tmp); _MergeSort(a, mid+1,right, tmp); //归并intbegin1=left, end1=mid; intbegin2=mid+1, end2=right; intindex=left; while (begin1<=end1&&begin2<=end2)//有一个子序列遍历完,循环结束 { if (a[begin1] <a[begin2])//升序,取小 { tmp[index++] =a[begin1++]; } else { tmp[index++] =a[begin2++]; } } //判断子序列是否遍历完,未遍历完毕的子序列剩余元素直接给到tmp数组while (begin1<=end1) { tmp[index++] =a[begin1++]; } while (begin2<=end2) { tmp[index++] =a[begin2++]; } //拷贝回去for (inti=left;i<=right;++i) { a[i] =tmp[i]; } } //归并排序voidMergeSort(int*a,intn) { int*tmp=(int*)malloc(sizeof(int)*n);//动态开辟与待排序数组大小相等的一片连续的空间_MergeSort(a,0,n-1,tmp);//子函数实现归并free(tmp);//释放动态开辟的空间} //打印voidPrint(int*a, intn) { for (inti=0;i<n;++i) { printf("%d ",a[i]); } } intmain() { inta[] = {10,6,7,1,3,9,4,2}; MergeSort(a,sizeof(a)/sizeof(a[0])); Print(a,sizeof(a)/sizeof(a[0])); return0; }
编辑
1.5 归并排序的特性总结:
1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(N)
4. 稳定性:稳定
至此归并排序的递归算法博主已经分享完了,相信大家对这个归并排序的逻辑有了一定的理解,大家可以自己动手敲敲代码,感受一下。
编辑
本期收录于博主的专栏——排序算法,适用于编程初学者,感兴趣的朋友们可以订阅,查看其它“常见排序”。排序算法_保护小周ღ的博客-CSDN博客
感谢每一个观看本篇文章的朋友,更多精彩敬请期待:保护小周ღ ——归并排序非递归算法
文章存在借鉴,如有侵权请联系修改删除!