做网站的旅行社,手机页面网站模板怎么卖,建站工具包,做公司网站流程目录
#x1f4a1;基本思想
#x1f4a1;图文介绍
#x1f4a1;动图演示
#x1f4a1;过程解释
#x1f4a1;代码实现
#x1f4a1;递归实现
#x1f4a1;非递归实现
#x1f4a1;总结 #x1f4a1;基本思想 归并排序#xff08;MERGE-SORT#xff09;是…目录
基本思想
图文介绍
动图演示
过程解释
代码实现
递归实现
非递归实现
总结 基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 图文介绍
动图演示 过程解释
分解为多个小区间 可以看到这种结构很像一棵完全二叉树分阶段可以理解为就是递归拆分子序列的过程递归深度为log2n。
合并相邻有序子序列 代码实现
递归实现 分割区间 以每个区间的中间位置为交界处将一个区间分割为两个区间。 int mid (begin end) / 2;//[begin,mid] [begin1,end]//先分再合并_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp); 返回条件 当区间内只剩下一个元素时我们可以认为该区间是有序的。 if (begin end){return;} 合并 合并是在分割完之后进行的类似于二叉树里面的后序遍历在递归的回归过程进行合并区间。合并时每次取较小的数尾插到tmp数组里合并结束后将tmp数组拷贝会原数组。 //[begin,mid] [begin1,end] 归并int begin1 begin, end1 mid;int begin2 mid1, end2 end;int i begin;//合并两个有序数组//有一个到了终止条件就停止循环while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])//取小的尾插 相等时取前一个尾插这样就是稳定的{tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//没循环完的直接尾插while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//拷贝回原数组memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1)); 完整代码
void _MergeSort(int* a, int begin, int end,int* tmp)
{if (begin end){return;}int mid (begin end) / 2;//[begin,mid] [begin1,end]//先分再合并_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);//[begin,mid] [begin1,end] 归并int begin1 begin, end1 mid;int begin2 mid1, end2 end;int i begin;//合并两个有序数组//有一个到了终止条件就停止循环while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])//取小的尾插 相等时取前一个尾插这样就是稳定的{tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//没循环完的直接尾插while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//拷贝回原数组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!);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
非递归实现 基本方法 非递归的实现方法是采用一种顺序合并就是直接以一个数作为一个区间然后进行两两合并一趟结束后再以两个数作为一个区间将区间两两合并以此类推。 int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//[begin1,end1][begin2,end2] 注意这种区间合并的方法可能会造成越界访问所以我们需要加判断条件又因为这里是在一趟合并结束后进行拷贝了所以当begin2和end1大于等于n时可以直接跳出这层循环而当end2n时则将end2n-1再进行合并。 //防止越界if (end1 n || begin2 n)break;if (end2 n){end2 n - 1;//直接合并} 完整代码
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc!);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//[begin1,end1][begin2,end2]//防止越界if (end1 n || begin2 n)break;if (end2 n){end2 n - 1;//直接合并}printf([%2d,%2d][%2d, %2d] , begin1, end1, begin2, end2);int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (jnbegin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//防止越界拷贝}printf(\n);gap * 2;}free(tmp);
} 总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
