环保公司网站建设方案,网络营销理论基础,dw做网站的导航栏,wordpress 4.8.6目录 1.归并排序的原理 2.实现归并排序
2.1框架
2.2区间问题和后序遍历
2.3归并并拷贝
2.4归并排序代码
2.5测试
3.非递归实现归并排序
3.1初次实现
3.2测试
3.3修改 3.4修改测试 1.归并排序的原理 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治…目录 1.归并排序的原理 2.实现归并排序
2.1框架
2.2区间问题和后序遍历
2.3归并并拷贝
2.4归并排序代码
2.5测试
3.非递归实现归并排序
3.1初次实现
3.2测试
3.3修改 3.4修改测试 1.归并排序的原理 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列 即先使每个子序列有序再使子序列段间有序 若将两个有序表合并成一个有序表称为二路归并。 可以将数组内容想象成一颗二叉树通过递归的方式将数组的内容分为左子树和右子树分出来的左子树和右子树又分别有它们的左子树和右子树。不断地向下进行拆分直到拆分到没有对应区间和区间只有一个元素(有序)的时候便递归返回。然后使用归并的方式将左子树和右子树归并成有序数组再将其拷贝会原数组这样对应的子树便会有序再递归返回不断地递归。直到根左子树和根右子树有序再归并和拷贝整个数组就会变得有序。 如图所示 2.实现归并排序 归并排序需要开额外的空间来辅助实现 之所以不在原数组实现是因为如果你使用交换的方式来进行排序可能会将原数组已经排好序的部分又一次变回无序而使用令数组向后移动的方式进行对应的排序时间复杂度便会大大增加因此归并排序可以理解成一种以空间换时间的排序方法。 归并排序需要开额外的空间但每次递归都要开空间显然是不合理的因此我们使用一个函数来完成递归的部分。思考一下新创建的函数的参数应该有哪些首先得有原数组其次得有我们开辟好的数组而我们要如二叉树一般形成对应的递归显然需要区间而区间的形成需要两个数来辅助因此可以传递两个代表区间的数进来可以取名为beginend(left,right)这样理解起来轻松一些。 2.1框架 2.2区间问题和后序遍历 如二叉树一般实现后序遍历注意 当beginend时代表着区间不存在或者只有一个元素(有序)的时候返回。因为是后序遍历需要先将区间的分界给计算出来之后才能使用。 2.3归并并拷贝 可以看出每次递归都会有两个区间的生成[begin,mid]和[mid1,end]我们的目标就是将这两个区间归并在一起这个很简单循环便可以搞定。注意两个区间不知道是哪个区间先完成循环因此在外面需要将未完成循环的区间补充回辅助数组中。 搞定完归并后使用memcpy将辅助数组中的内容拷贝回原数组排序便结束了。注意我们传递的是闭区间因此拷贝的长度为end-begin1 2.4归并排序代码
void MergeSort(int*arr,int n)
//将数组和数组的元素个数传递过来
{int* a (int*)malloc(sizeof(int)*n);//创建辅助数组if (a NULL){perror(malloc fail);return;}_MergeSort(arr,a,0,n-1);free(a);
}
void _MergeSort(int*arr,int*a,int begin ,int end)
{//检验区间是否有效if (begin end){return;}//后序遍历int mid (begin end) / 2;//新区间为[begin,mid],[mid1,end]_MergeSort(arr,a,begin,mid);_MergeSort(arr,a,mid1,end);//归并int begin1 begin; int end1 mid;int begin2 mid1; int end2 end;//两个区间int index begin;//新区间第一个元素的下标while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){a[index] arr[begin1];}else{a[index] arr[begin2];}}while (begin1 end1){a[index] arr[begin1];}while (begin2 end2){a[index] arr[begin2];}//将归并好的内容拷贝回原数组memcpy(arrbegin,abegin,(end-begin1)*sizeof(int));
}
2.5测试 3.非递归实现归并排序 根据我们之前的排序我们可以看到它的本质是和预排序差不多的形态因此我们可以通过一个整型如gap来区分一个元素和一个元素排序两个元素和两个元素排序....... 3.1初次实现
void MergeSortNonR(int* arr, int n)
{int* a (int*)malloc(sizeof(int) * n);//创建辅助数组int gap 1;//gap1便是1个元素和1个元素归并while (gap n){int i 0;for (i 0; i n; i 2 * gap)//i2*gap跳过一整个区间{//两个区间int begin1 i; int end1 i gap - 1;int begin2 i gap; int end2 i 2 * gap - 1;int index i; //新区间第一个元素的下标//归并while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){a[index] arr[begin1];}else{a[index] arr[begin2];}}while (begin1 end1){a[index] arr[begin1];}while (begin2 end2){a[index] arr[begin2];}memcpy(arr i, a i, sizeof(int) * (2 * gap));}gap * 2;}free(a);
}
3.2测试
出现了越界问题 程序在打印之前就被迫中止了 3.3修改 观察可以发现第一个区间的为[begin1,end1]第二个区间为[begin2,end2]那么begin1必然不会越界而end1和更后面的begin2end2都可能会越界。而其中end1和begin2越界的话都在说明已经排好序了而end2越界begin2没越界则在说明还有数据未被排序。 再想一想细节end1越界了begin2一定越界而begin2越界end1不一定越界所以无需考虑end1越界只要begin2越界就说明排序已完成直接break 而只有end2越界便将end2修正成数组的最大下标即可。 注意我们之前使用拷贝函数均是拷贝2*gap个过去在这里显然不合适总区间长度应修正 为end2-begin1这个修正不应该放在最后因为在进行归并的期间begin1会至end1 也不应该放在判断begin2end2越界之前因为可能会对end2进行修正。综上所述得出的代码为 void MergeSortNonR(int* arr, int n)
{int* a (int*)malloc(sizeof(int) * n);//创建辅助数组int gap 1;//gap1便是1个元素和1个元素归并while (gap n){int i 0;for (i 0; i n; i 2 * gap)//i2*gap跳过一整个区间{//两个区间int begin1 i; int end1 i gap - 1;int begin2 i gap; int end2 i 2 * gap - 1;if (begin2 n){break;}if (end2 n)end2 n - 1;//修正区间长度int order end2 - begin11;//修正要拷贝的长度int index i; //新区间第一个元素的下标//归并while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){a[index] arr[begin1];}else{a[index] arr[begin2];}}while (begin1 end1){a[index] arr[begin1];}while (begin2 end2){a[index] arr[begin2];}/*int order 2 * gap;if (2 * gap n){order n;}*/memcpy(arr i, a i, sizeof(int) * order);}gap * 2;}free(a);
} 3.4修改测试 至此归并排序的递归版和非递归版讲解完成感谢各位友友的来访祝各位友友前程似锦O(∩_∩)O
