归并排序（递归与非递归写法）

本文同步发布在CSDN：https://blog.csdn.net/weixin_44385565/article/details/94588321

归并排序的基本操作是将两个有序数组合并成一个有序数组，原理是运用分治思想，递归地将一个数组的左右两部分有序数列进行归并。

C/C++的递归实现：

 1 // mergeSort.cpp : 递归写法
 2 //
 3 
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 #define elementType int//自定义数据类型
 7 using namespace std;
 8 
 9 void mergeSort(elementType A[], int N);//N为数组大小，统一函数接口
10 void mSort(elementType A[], elementType tmpA[], int L, int rightEnd);//传入左右边界
11 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd);//将有序的两个部分进行归并
12 
13 
14 int main()
15 {
16     int N;//数组大小
17     scanf("%d", &N);
18     elementType* A = (elementType*)malloc(N * sizeof(elementType));
19     for (int i = 0; i < N; i++)
20         cin >> A[i];
21     mergeSort(A, N);
22     for (int i = 0; i < N; i++)
23         cout << A[i] << " ";
24     return 0;
25 }
26 
27 void mergeSort(elementType A[], int N) {
28     elementType* tmpA = (elementType*)malloc(N * sizeof(elementType));//申请内存建立临时数组
29     if (tmpA != NULL) {
30         mSort(A, tmpA, 0, N - 1);
31         free(tmpA);
32     }
33     else
34         printf("Error!
");//内存申请失败
35 }
36 
37 void mSort(elementType A[], elementType tmpA[], int L, int rightEnd) {
38     if (L < rightEnd) {
39         int center = (L + rightEnd) / 2;
40         mSort(A, tmpA, L, center);
41         mSort(A, tmpA, center + 1, rightEnd);
42         merge(A, tmpA, L, center + 1, rightEnd);
43     }
44 }
45 
46 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd) {
47     int tmpL = L,
48         leftEnd = R - 1,
49         elementNum = rightEnd - L + 1;
50     while (L <= leftEnd && R <= rightEnd) {
51         if (A[L] < A[R])
52             tmpA[tmpL++] = A[L++];
53         else 
54             tmpA[tmpL++] = A[R++];
55     }
56     while (L <= leftEnd)
57         tmpA[tmpL++] = A[L++];
58     while (R <= rightEnd)
59         tmpA[tmpL++] = A[R++];
60     for (int i = 0; i < elementNum; i++, rightEnd--)
61         A[rightEnd] = tmpA[rightEnd];
62 }

C/C++的非递归写法：

 1 // mergeSort_without_recursion.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
 2 //归并排序的非递归写法
 3 
 4 #include <iostream>
 5 #define elementType int
 6 using namespace std;
 7 
 8 void mergeSort(elementType A[], int N);
 9 void mSort(elementType A[], elementType tmpA[], int length, int N);
10 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd);
11 
12 int main()
13 {
14     int N;
15     scanf("%d", &N);
16     elementType* A = (elementType*)malloc(N * sizeof(elementType));
17     for (int i = 0; i < N; i++)
18         cin >> A[i];
19     mergeSort(A, N);
20     for (int i = 0; i < N; i++)
21         cout << A[i] << " ";
22     return 0;
23 }
24 
25 void mergeSort(elementType A[], int N) {
26     elementType* tmpA = (elementType*)malloc(N * sizeof(elementType));
27     if (tmpA != NULL) {
28         int length = 1;
29         while (length < N) {
30             mSort(A, tmpA, length, N);
31             length *= 2;
32             mSort(tmpA, A, length, N);
33             length *= 2;
34         }
35         free(tmpA);
36     }
37     else
38         printf("Error!
");//内存申请失败
39 }
40 
41 void mSort(elementType A[], elementType tmpA[], int length, int N) {
42     int i;
43     for (i = 0; i <= N - length * 2; i += length * 2)
44         merge(A, tmpA, i, i + length, i + length * 2 - 1);
45     if (i < N - length)//还剩两个子列，将它们归并到tmpA
46         merge(A, tmpA, i, i + length, N - 1);
47     else//剩下最后一个子列，直接复制到tmpA
48         for (int j = i; j < N; j++)
49             tmpA[j] = A[j];
50 }
51 
52 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd) {
53     int tmpL = L,
54         leftEnd = R - 1;
55     while (L <= leftEnd && R <= rightEnd) {
56         if (A[L] < A[R])
57             tmpA[tmpL++] = A[L++];
58         else
59             tmpA[tmpL++] = A[R++];
60     }
61     while (L <= leftEnd)
62         tmpA[tmpL++] = A[L++];
63     while (R <= rightEnd)
64         tmpA[tmpL++] = A[R++];
65 }