目录
前言
递归实现
代码实现
非递归实现
代码实现
总结
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
在我们前边的学习过程中,例如合并两个有序数组等问题,我们就使用过归并的思想,本质上来说归并排序还是分治的思想,将大问题化为小问题,然后解决小问题,最终是实现大问题的解决。
动图演示
归并排序的递归实现并不复杂,有以下几个步骤:
1.首先申请一段空间tmp,用来保存以及排好序的部分数据,当所有数据都排序完后,重新拷贝回原数组。
2.对数组数据进行分割,例如二叉树分为左右子树一样,也将数组分割为左右数组,知道左指针left大于等于右指针right时,返回。
3.对以及递归好的数据进行排序,两个区域内的数据进行比较,小的数据插入到tmp数组中,直至到数组的最后一个数据,如果当一个数组提前结束,直接将另外一个数组数据直接拷贝即可。
4.将排序好的tmp数组拷贝回原数组。
由于原函数不适合递归,所以我们定义子函数,并且求出left和right进行递归,将数组分为[left,mid]和[mid+1,right]两个部分,切记free我们申请的空间,其余按照思路实现即可。
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = left + (right - left) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int i = left;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;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++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}
}
void MergeSort(int* a, int n)
{int left = 0;int right = n - 1;int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, left, right, tmp);free(tmp);tmp = NULL;
}
归并的非递归实现起来比递归实现较难一点,但是还是分治的思想,只不过非递归有点类似于二叉树的后序遍历,我们使用gap来控制每次归并时数组内数据个数,例如第一次就是一个一个数据归并成两个数据的有序数组,第二次使用两个数据的有序数组归并成四个数据的有序数组,所以gap是由1开始,并且每次乘2。
非递归实现就是在gap等于1时,将整个数组元素排序成两个两个有序,这个递归实现是不同的。
但是当我们每次将gap乘2时,我们发现数组元素个数不一定是2的次方倍,所以不进行处理时,我们的数组一定会造成越界访问。
我们对每次要归并的数组,第一个数组起始为begin1,结束为end1,第二个数组起始为begin2,结束为end2,所以就会有以下三种情况越界:
1.end1越界,即end1>=n。
2.begin2越界,即begin2>n。
3.end2越界,即end2>=n。
所以我们要对边界进行修正,当边界>=n时,我们将其赋值为n-1,修正如下:
if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}
我们注意到当begin1>=n时,我们将begin2 赋值为n,end2赋值为n-1,我们发现这样的话这段区间就不存在了,这是为什么呢,我们来探究一下。
我们对程序进行以上的处理,发现程序崩溃了,通过调试发现是tmp数组越界了,那么tmp数组为什么会越界呢?
通过测试发现,本来只有十个数据,所以下标最多到9,但是tmp数组的下标10的位置插入元素,导致越界,这是因为当[begin2,end2]原本不存在,但是我们修正让其存在[9,9],多插入一个数据,所以导致越界,所以我们做一下修改。
处理过后就没有下标的越界了。
当我们解决这个问题之后,其余代码按照思路实现就好了。
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("maolloc fail");exit(-1);}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;int InDex = i;if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}/*printf("[%d,%d] ", begin1, end1);printf("[%d,%d] ", begin2, end2);*/while (begin1 <= end1 && begin2 <= end2){//printf("%d ", InDex);if (a[begin1] < a[begin2]){tmp[InDex++] = a[begin1++];}else{tmp[InDex++] = a[begin2++];}}while (begin1 <= end1){//printf("%d ", InDex);tmp[InDex++] = a[begin1++];}while (begin2 <= end2){//printf("%d ", InDex);tmp[InDex++] = a[begin2++];}}for (int j = 0; j < n; j++){a[j] = tmp[j];}gap *= 2;}free(tmp);tmp = NULL;
}
我们今天讲解了归并排序的递归和非递归的实现方法,码文不易,希望可以对大家有所帮助。
上一篇:软件设计师考试准备二
下一篇:JVM——类文件结构