广州商城型网站,手机制作封面教程网站,网站维护一般需要多久,图片上传 网站建设教学视频教程1. 归并排序原理#xff1a;
归并排序的大概原理如下图所示#xff1a; 从图中可以看出#xff0c;归并排序的整体思路就是把已给数组不断分成左右两个区间#xff0c;当这个区间中的数据数量到达一定数值时#xff0c;便返回去进行排序#xff0c;整体的结构类似二叉树…1. 归并排序原理
归并排序的大概原理如下图所示 从图中可以看出归并排序的整体思路就是把已给数组不断分成左右两个区间当这个区间中的数据数量到达一定数值时便返回去进行排序整体的结构类似二叉树的结构因此对于归并排序同样可以利用递归进行实现。 对于递归实现归并排序首先需要实现的第一步便是如何区分左右区间在快速排序中虽然在递归时依然同样需要根据一个值来区分左右区间但是用于区分左右区间的值是在左右两边遍历数组时自动选出来的对于归并排序通过观察可以发现归并排序的左右区间是通过数组下标的中间值进行区分的为了方便表示将这个中间值命名为例如数组在进行第一次区分左右区间时左区间的范围是,右区间的范围是通过计算不难得到所以对于数组左右区间的划分可以通过(数组下标起始),(数组下标末位来划分即 左区间范围 右区间范围 同时在图中当区间中的数值数量为后下一步直接进行排序此处图中省略了区间分为两个区间数值数量为的两个区间的过程这是因为在区间中的数值数量时便停止划分区间
所以对于区间划分这部分的递归可以用代码表示为 //归并排序void _MergeSort(int* a, int begin, int end){if (begin end){return;}int mid (begin end) / 2;MergeSort(a, begin, mid);MergeSort(a,mid 1, end);}
在区间划分结束后就需要对数组进行排序。这里需要注意在进行排序时不能直接在原本已有的数组进行排序为了解决这个问题本文选择独立开辟一块空间用于排序当一部分区间在这部分空间排序完成后便将这部分内容返回到原数组开辟空间的过程如下 void MergeSort(int* a, int begin, int end){int* tmp (int*)malloc(sizeof(int) * (end - begin 1));if (tmp NULL){perror(malloc fail);}_MergeSort(a, tmp, begin, end);}
因为开辟的空间需要在上面的函数中使用所以对于函数的定义需要更改为上图中的格式。
对于如何排序文章给出下面的方法
对于一个区间定义四个变量分别为,,具体使用方法如下
令,,,,具体使用方法如下方的代码所示 //归并排序void _MergeSort(int* a,int* tmp, int begin, int end){if (begin end){return;}int mid (begin end) / 2;_MergeSort(a,tmp, begin, mid);_MergeSort(a,tmp,mid 1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int index begin;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];}memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));}
为了方便解释代码内容给出下面的图像 首先对左右区间进行区分期间各个区间的,,如图所示当区间数据数量时停止区分区间进行排序例如对这个区间如果则让小的哪个值插入到此时中的内容如下图所示 向原数组拷贝数值后原数组左区间数值如下 在区间遍历完成后再遍历区间由于 的不同再数据调整完拷贝到后数组内容为 随后再向原数组中拷贝原数组内容为 对于其他的序列依旧按照此规律此部分不再叙述。
测试函数如下
void TestMergeSort()
{int i[] { 10,6,7,1,3,9,4,2 };int size sizeof(i) / sizeof(int);MergeSort(i, 0, size - 1);printf(归并排序);ArrayPrint(i, size);
}
运行结果如下
