赞
踩
目录
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并
- void _MergeSort(int* a, int begin, int end, int* tmp)
- {
- if (begin == end)//递归的结束条件
- {
- return;
- }
-
- int midi = (begin + end) / 2;//作为分割线
- _MergeSort(a, begin, midi,tmp);//递归左区间,让左区间有序
- _MergeSort(a, midi + 1, end,tmp);//递归右区间,让右区间有序
-
- int begin1 = begin;//左右区间都有序后,归并两区间内的数据
- int end1 = midi;
- int begin2 = midi + 1;
- int end2 = end;
- int i = begin;
- while (begin1 <= end1 && begin2 <= end2)//归并两区间内的数组数据,两数组中有一方遍历结束就结束了
- {
- if (a[begin1] <=a[begin2])//较小者插入tmp数组中
- {
- tmp[i++] = a[begin1++];
- }
- else
- {
- tmp[i++] = a[begin2++];
- }
- }
-
- while (begin1 <= end1)//若是两数组长度不一致,且数组1长度>数组2,则把数组1的剩余的所有数据插入到tmp中
- {
- tmp[i++] = a[begin1++];
- }
-
- while (begin2 <= end2)//数组2长度>数组1,把数组2剩余的所有数据插入到tmp中
- {
- tmp[i++] = a[begin2++];
- }
-
- memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//整个区间在tmp数组归并有序后拷贝至a数组中原来的位置
-
- }
-
- void MergeSort(int* a, int n)
- {
- int* tmp = (int*)malloc(sizeof(int) * n);//用来归并
- _MergeSort(a, 0, n - 1, tmp);
- return 0;
- }
递归的结束条件:begin==end(即区间仅有1个值)那么整个区间已经有序,无需递归让它有序了
采用临时数组tmp的原因:直接在原数组内进行归并会导致覆盖
对于无序的区间:
1 将整个区间划分为左右区间
2 递归使得左区间有序 递归使得右区间有序
3 左右区间都有序后,对左右区间中的数组数据进行归并:(按升序)
每一轮比较得两数组中较小者,插入到临时数组tmp中
结束条件:两数组中有一方遍历完循环就结束了
注意:可能存在一个数组遍历完,另一方还没遍历完的情况,所以需要让未遍历完的数组直接全部插入到tmp数组中,无需再比较
4 将再tmp数组中归并得到的整个有序区间拷贝至原数组空间
- void MergeSortNonR(int* a, int n)
- {
- int* tmp = (int*)malloc(sizeof(int) * n);
- int gap = 1;//一一归,两两归,四四归……
- while (gap < n)
- {
- //某数字归:
- int i = 0;
- int j = 0;
- for (i = 0; i < n; i+=2*gap)//某数字归中的所有大组的归并有序
- {
- //一大组中的两小组的归并有序
- int begin1 = i;
- int end1 = i + gap - 1;
- int begin2 = i + gap;
- int end2 = i + 2 * gap - 1;
-
- if (end1 >= n || begin2>=n)//两小组中仅有存在第一组,且第一组的个数不足,第二组完全不存在 or//两小组中第一组完整存在(个数足够),第二组完全不存在
- {
- break;//不用进行归并,第一组的有效数据直接留在原数组
- }
-
- else if (end2 >= n)//第一组完全存在,第二组存在一部分(个数不足)
- {
- end2 = n - 1;//更正end2的范围
- }
-
- 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 (begin2 <= end2)
- {
- tmp[j++] = a[begin2++];
- }
-
- memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//归并一大组,拷贝一大组
- }
- gap *= 2;//某数字归的迭代,比如由--归变成两两归……
- }
- free(tmp);
- }
注意:两小组(用于归并的两个组)的下标可能发生越界,即本来规定的每小组的数据个数应该是那么多,但是可能出现某小组个数不足的情况,那这时候下标就会越界:
有两种解法方法:
法一:归并一组,拷贝一组,两小组中有一方不存在的那这两小组不用归并,直接让存在的那一组留在原数组,如情况1、情况2
若是两小组都存在,但是有一组是部分存在,那就修正越界的那一部分,对两小组有效的数据归并 ,如情况3
如上面的代码实现1
法二:整组归并到tmp数组后再整组拷贝至原数组
对于情况1:不用执行两组的归并(有一组不存在),且修正第一组的范围,让第一组的所有有效数据直接拷贝插入到tmp
不执行归并的方法:将第二组的范围设为不存在
对于情况2:不执行两小组的归并,只需将 将第二组的范围设为不存在,让第一组的所有有效数据直接拷贝插入到tmp
对于情况3: 两小组均有存在的有效数据,可以进行归并,只需修正第二组越界的范围
如下面的代码实现2
- void MergeSortNonR(int* a, int n)
- {
- int* tmp = (int*)malloc(sizeof(int) * n);
- int gap = 1;
- while (gap < n)
- {
- int i = 0;
- int j = 0;
- for (i = 0; i < n; i+=2*gap)
- {
- int begin1 = i;
- int end1 = i + gap - 1;
- int begin2 = i + gap;
- int end2 = i + 2 * gap - 1;
-
- if (end1 >= n)//两小组不会进行归并,且需修改更正第一组的有效范围,让第一组直接拷贝到tmp数组中
- {
- end1 = n - 1;
- begin2 = n;
- end2 = n - 1;
- }
- else if (begin2 >= n)//两小组不会进行归并,第一组直接拷贝到tmp数组中
- {
- begin2 = n;
- end2 = n - 1;
- }
- else if(end2>=n)//两小组会进行归并,只需修正第二组越界的范围
- {
- end2 = n - 1;
- }
-
- 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 (begin2 <= end2)
- {
- tmp[j++] = a[begin2++];
- }
- }
- memcpy(a, tmp, sizeof(int) * n);//整组归并有序后整组拷贝至原数组
- gap *= 2;
- }
- free(tmp);
- }
总结:
归并排序的非递归实现的坑点比较多,有代码实现1和代码实现2
代码实现1就是归并一组,拷贝一组,代码实现2是整租归并有序后再整组拷贝至原数组
坑点:注意三种数组范围越界的情况
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。