福州网站建设工作室,怎样做百度推广,海南乐秀同城群软件下载,网站建设基础 ppt1.基本思想
归并排序#xff08;MERGE-SORT#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法#xff08;Divide andConquer#xff09;的一个非常典型的应用。 将已有序的子序列合并#xff0c;得到完全有序的序列#xff0c;即先使每个子序列有序…1.基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。有点像二叉树递归大家可以联想二叉树理解 下面是动图展示
2.代码展示及讲解
讲解部分在注释中配合上述两张图食用更佳
#include stdio.hvoid _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end){return;}//递归返回的判断条件int mid (begin end) / 2;//作为数组递归的左边类似于左子树和右边右子树_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);//对数组递归利用mid将数组分成左右两个数组并分别不断递归并将递归排列好的元素储存到辅助数组tmp中然后用内存函数将tmp中的元素复制到原数组中int left1 begin;int right1 mid;int left2 mid 1;int right2 end;//递归的左右边界int t begin;while (left1 right1 left2 right2){if (a[left1] a[left2]){tmp[t] a[left1];}else{tmp[t] a[left2];}}while (left1 right1){tmp[t] a[left1];}while (left2 right2){tmp[t] a[left2];}// 在递归的过程中对左右两边进行排序如果上述排序方法一下子看不懂的话//可以在纸上模拟一下绝对简单就是将两个数组中的元素按照从小到大依次放到辅助数组tmp中memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));//转移排好的元素
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);**//创建一个新数组作为辅助数组储存递归的元素并将其进行排序//然后使用内存函数将辅助数组中的排列好的元素转移到原数组中**if (tmp NULL){perror(malloc fail);return;}//判断空间是否开辟成功_MergeSort(a, 0, n - 1, tmp);//借助子函数开始递归
}int main()
{int a[10] { 1,3,5,7,9,2,4,6,8,10 };MergeSort(a, 10);for (int i 0; i 10; i){printf(%d , a[i]);}return 0;
}3.归并排序的特性总结 归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 以上就是关于C中的类的6个默认成员函数详解的全部内容希望我的文章能对你有所帮助 感谢你的观看
