点击刷新
归并排序是一种基于“归并”思想的排序方法，本节主要介绍其中最基本的2-路归并排序。2-路归并排序的原理是，将序列两两分组，将序列归并为[n/2]个组，组内单独排序；然后将这些组再两两归并，生成[n/4]个组，组内再单独排序；以此类推，直到只剩下一个组为止，其核心在于如何将两个有序序列合并成一个有序序列。归并排序的时间复杂度为O(nlogn)。
下面来看一个例子，要将序列{66，12，33，57，64，27，18）进行2-路归并排序。
①第一趟。两两分组，得到四组：{66，12}、{33，57}、{64，27}、{18}，组内单独排序，
得到新序列{{12,66}，{33，57}，{27，64}，{18}}。
②第二趟。将四个组继续两两分组，得到两组：{12，66，33，57}、{27，64，18}，组内单
独排序，得到新序列{{12，33，57，66}，{18，27，64}}
③第三趟，将两个组继续两两分组，得到一组：{12，33，57，66，18，27，64}，组内单独排
序，得到新序列{12，18，27，33，57，64，66}，算法结束。
从上面的过程中可以发现，2-路归并排序的核心在于如何将两个有序序列合并为一个有
序序列，而这个过程在上一小节的“序列合并问题”中已经讲解。接下来讨论2-路归并排序
的递归版本和非递归版本的具体实现。
1.递归实现
2-路归并排序的递归写法非常简单，只需要反复将当前区间[eft，nightl分为两半，对两个
子区间et mid]与[mid+l，rnght]分别递归进行归并排序，然后将两个已经有序的子区间合并
为有序序列即可，代码如下，其中merge函数为上一节的代码改编而来，请读者注意与上一
节代码的对比：
递归实现：
#include<cstdio> #include<cmath> using namespace std; const int maxn = 100; int n,A[maxn]; int min(int a, int b) { return a < b ? a : b; } //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[], int L1, int R1, int L2, int R2) { int i = L1, j = L2; //i指向A[l1],j指向A[L2] int temp[maxn], index = 0; //temp临时存放合并后的数组，index为其下标 while (i <= R1 && j <= R2) { if (A[i] <= A[j]) { //如果A[i]<=A[j] temp[index++] = A[i++]; //将A[i]加入序列temp } else { // 如果A[i]>A[j] temp[index++] = A[j++]; //将A[j]加入序列temp } } while (i <= R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp while (j <= R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp for (i = 0; i < index; i++) { A[L1 + i] = temp[i]; //将合并后的序列赋值回数组A } } void mergeSort(int A[], int left, int right) { if (left <right) { int mid = (left + right) / 2; mergeSort(A, left, mid); mergeSort(A, mid + 1, right); merge(A, left, mid, mid + 1, right); } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &A[i]); } mergeSort(A,0,n-1); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; }
非递归实现：
2-路归并排序的非递归实现主要考虑到这样一点：每次分组时组内元素个数上限都是2的幂次。于是就可以想到这样的思路：令步长step的初值为2，然后将数组中每step个元素作为一组，将其内部进行排序(即把左step/2个元素与右sep/2个元素合并，而若元素个数不超过step/2，则不操作)；再令step乘以2，重复上面的操作，直到step/2超过元素个数n。
#include<cstdio> #include<cmath> using namespace std; const int maxn = 100; int n,A[maxn]; int min(int a, int b) { return a < b ? a : b; } //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[], int L1, int R1, int L2, int R2) { int i = L1, j = L2; //i指向A[l1],j指向A[L2] int temp[maxn], index = 0; //temp临时存放合并后的数组，index为其下标 while (i <= R1 && j <= R2) { if (A[i] <= A[j]) { //如果A[i]<=A[j] temp[index++] = A[i++]; //将A[i]加入序列temp } else { // 如果A[i]>A[j] temp[index++] = A[j++]; //将A[j]加入序列temp } } while (i <= R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp while (j <= R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp for (i = 0; i < index; i++) { A[L1 + i] = temp[i]; //将合并后的序列赋值回数组A } } void mergeSort(int A[]) { //step为组内元素个数，step/2为左子区间元素个数 for (int step = 2; step / 2 < n; step *= 2) { //每step个元素一组，组内前step/2和后step/2个元素进行合并 for (int i = 0; i <= n-1; i += step) { //对每一组 int mid = i + step / 2 - 1; //左子区间元素个数为step/2 if (mid + 1 <= n-1) { //右子区间存在元素则合并 //左子区间为[i,mid],右子区间为[mid+1,min(i+step-1,n)] merge(A, i, mid, mid + 1, min(i + step - 1, n-1)); } } } } int main(){ scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &A[i]); } mergeSort(A); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; }
当然，如果题目中只要求给出归并排序每一趟结東时的序列，那么完全可以使用sort函数来代替 merge函数(只要时间限制允许)，如下所示:
如果使用sort()函数进行实现： #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn = 100; int n, A[maxn]; int min(int a, int b) { return a < b ? a : b; } //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[], int L1, int R1, int L2, int R2) { int i = L1, j = L2; //i指向A[l1],j指向A[L2] int temp[maxn], index = 0; //temp临时存放合并后的数组，index为其下标 while (i <= R1 && j <= R2) { if (A[i] <= A[j]) { //如果A[i]<=A[j] temp[index++] = A[i++]; //将A[i]加入序列temp } else { // 如果A[i]>A[j] temp[index++] = A[j++]; //将A[j]加入序列temp } } while (i <= R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp while (j <= R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp for (i = 0; i < index; i++) { A[L1 + i] = temp[i]; //将合并后的序列赋值回数组A } } void mergeSort(int A[]) { //step为组内元素个数，step/2为左子区间元素个数 for (int step = 2; step / 2 < n; step *= 2) { //每step个元素一组，组内[i,min(i+step,n+1)]进行排序 for (int i = 0; i <= n-1; i += step) { sort(A + i, A + min(i + step, n )); } //此处可以输出归并排序的某一趟结束的序列 } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &A[i]); } mergeSort(A); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; }
© 著作权归作者所有
发表评论
