铜川市住房和城乡建设局网站,新乡最新消息,国内优秀的设计网站推荐,无锡做网站企业归并排序 前言一、归并排序递归实现#xff08;1#xff09;归并排序的核心思路#xff08;2#xff09;归并排序实现的核心步骤#xff08;3#xff09;归并排序码源详解#xff08;4#xff09;归并排序效率分析1#xff09;时间复杂度 O#xff08;N*logN#xf… 归并排序 前言一、归并排序递归实现1归并排序的核心思路2归并排序实现的核心步骤3归并排序码源详解4归并排序效率分析1时间复杂度 ON*logN2空间复杂度 ON稳定性稳定 二、归并排序的非递归实现1 关于递归的缺点的讨论 2 归并排序 非递归算法实现思路3码源详解4运行结果 前言
快速排序前序 归并排序后序 一、归并排序递归实现
1归并排序的核心思路
将 已有序的子序列 合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 2归并排序实现的核心步骤 向下递归 对半分割 。递归返回条件递归到最小1个即是有序 [ 控制的是范围 归并的区间 ]递归到最深处最小时就递归回去开始分按对半分割分出的范围 将 已有序的子序列 合并在 tmp 里进行归并。再将tmp里形成的有序序列拷贝回原数组 【 因为下一次递归回去上一层再进行下一次的归并过程中会将数据在tmp中进行归并会将tmp中的数据覆盖所以要及时将小部分已归并排好序的子序列拷贝回原数组 】再进行递归返回上一层的递归归并直到递归层数都结束。 3归并排序码源详解
void _MergeSort(DataType* a, DataType* tmp, int begin, int end) {if (beginend) { //递归返回的条件不正常的的范围 或 只剩1个数return;}int mid (begin end) / 2;//先递归到最小//[begin,mid][mid1,end]_MergeSort(a, tmp, begin, mid); //数组是从0开始所以endmid-1这样设计_MergeSort(a, tmp, mid1, end);//再进行归并 —— 所以归并的过程设计在递归后面后序//归并到tmp数组再拷贝回去int begin1 begin; int end1 mid;int begin2 mid 1; int end2 end;int index begin; //指向tmp,begin是 根据要进行比较插入的数组的位置 找到其对应在tmp中所对应的位置则不会覆盖前面已经排好序的数据//原型合并两组数且有序while (begin1 end1 begin2 end2) { //其中一组满足了条件就不再继续就跳出循环if (a[begin1] a[begin2]) {tmp[index] a[begin1];}else {tmp[index] a[begin2];}} while (begin1 end1) { //把剩下还没插入tmp的插入进去tmp[index] a[begin1];}while (begin2 end2) { //把剩下还没插入tmp的插入进去tmp[index] a[begin2];}//拷贝回原数组//source dest 拷贝的数组大小memcpy(abegin,tmpbegin,sizeof(DataType)*(end-begin1));
}void MergeSort(DataType* a, int n) {DataType* tmp (DataType*)malloc(sizeof(DataType) * n); //开辟新的数组临时存放用于归并排序过程if (tmp NULL) {perror(malloc fail);return;}//将 待排序的数组、归并过程用的tmp临时数组、归并范围 传过去_MergeSort(a, tmp, 0, n - 1); //因为 主函数中有malloc tmp的操作若递归调用主函数则每次调用都会malloc再free 是对空间上的浪费//因此用子函数进行递归 【_子函数】free(tmp);
}4归并排序效率分析
1时间复杂度 ON*logN
二分 有 logN 层 也正是因为是logN层递归深度不会太深所以不用考虑非递归当然非递归也能实现。 每层有N个数进行归并排序
N*logN
2空间复杂度 ON
开辟了个 空间大小为N的 新的数组用于归并有序的过程。 在原数组上归并会出现什么问题
会覆盖数据最小的1换到8的位置后8和7就不再保持有序了。
稳定性稳定 二、归并排序的非递归实现
归并排序是 二分的思想 logN层 递归不会太深、且现编译器优化后递归、非递归的性能差距没有那么大了 所以不用考虑非递归但非递归实现也不难。下面带大家简单实现一下。
1 关于递归的缺点的讨论
递归的缺点递归消耗栈帧递归的层数太深容易爆栈。 【栈的空间比较小在x86(32位)环境下只有8M。对比同一环境下的堆则有2G。因为平时函数调用开不了多少个栈帧。理论上递归深度1w 可能就会爆 但实际上5k左右就爆掉了】
这时就需要改非递归了
★递归—非递归
改循环利用 [ 数据结构 ] 栈本质上是通过malloc 在堆上开辟的内存空间内存空间足够大递归逆着来求如斐波那契数列逆着来求也是可行的【归并排序的非递归实现 也是个很好的例子】 而归并排序的非递归实现则是用到了其中的第三点 。 2 归并排序 非递归算法实现思路
虽说不是递归是递归的逆序版。是直接从最深层次逆序回去直接开始归并排序免去了向下深入递归。虽说不是递归但也算是递归的思路的另一个种实现。
开辟新的数组临时存放用于归并排序过程int gap1gap*2【gap控制归并的范围11归并22归并44归并】for (int i 0; i n; i 2 * gap) { 【i 控制进行比较轮到的组号控制进行归并的组号】归并完一轮将归并好的有序数组拷贝回原数组memcpy 。进入新的一轮归并直至gapn则归并完成
☆注意的两个情况 6. if (begin2 n) { break; } 第二组不存在这一组不用归并了 7. if (end2 n) { end2 n - 1; } 第二组右边界越界问题修正一下 3码源详解
//归并排序——非递归版 从最底层开始逆着往回求如同斐波那契
void MergeSortNonR(DataType* a,int n) {DataType* tmp (DataType*)malloc(sizeof(DataType) * n); //开辟新的数组临时存放用于归并排序过程if (tmp NULL) {perror(malloc fail);return;}int gap 1;while (gap n) { //gap控制 11归并22归并44归并//i控制进行比较轮到的组号控制归并的组号for (int i 0; i n; i 2 * gap) { //可以通过画出数组在草稿纸上演示理清要比较的数begin1、end1、begin2、end2之间和i、gap的数量关系//[begin1,end1][begin2,end2]归并 int begin1 i; int end1 i gap - 1; //-1 控制下标的边界int begin2 i gap; int end2 i 2 * gap - 1;//如果第二组不存在这一组不用归并了if (begin2 n) {break;}//第二组右边界越界问题修正一下if (end2 n) {end2 n - 1;}int index i;while (begin1 end1 begin2 end2) { // 其中一组不满足了条件了其中一个数组遍历完了就不再继续就跳出循环 if (a[begin1] a[begin2]) { //两个数组比对小的放进去tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1) { //把剩下的没遍历进去的数组剩余的部分 遍历进去tmp[index] a[begin1];}while (begin2 end2) {tmp[index] a[begin2];}//拷贝回原数组//通过ai、tmpi来找到要拷贝数组部分的对应下标memcpy(a i, tmp i,(end2-i1)*sizeof(DataType));}printf(\n);gap * 2; //gap控制总体归并}free(tmp);
}4运行结果
