归并排序
标签：scanf 数列 free ges return mergesort efi malloc printf
本文同步发布在CSDN：https://blog.csdn.net/weixin_44385565/article/details/94588321
归并排序的基本操作是将两个有序数组合并成一个有序数组，原理是运用分治思想，递归地将一个数组的左右两部分有序数列进行归并。
C语言实现：
1 #include 2 #include 3 #define elementType int
4
5 void mergeSort(elementType A[], int N);//N为数组大小，统一函数接口
6 void mSort(elementType A[], elementType tmpA[], int L, int rightEnd);//传入左右边界
7 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd);//将有序的两个部分进行归并
8
9
10 int main()
11 {
12 int N;
13 scanf("%d", &N);
14 elementType* A = (elementType*)malloc(N * sizeof(elementType));
15 for (int i = 0; i )
16 scanf("%d", &A[i]);
17 mergeSort(A, N);
18 for (int i = 0; i )
19 printf("%d ", A[i]);
20 return 0;
21 }
22
23 void mergeSort(elementType A[], int N) {
24 elementType* tmpA = (elementType*)malloc(N * sizeof(elementType));//申请内存建立临时数组
25 if (tmpA != NULL) {
26 mSort(A, tmpA, 0, N - 1);
27 free(tmpA);
28 }
29 else
30 printf("Error!\n");//内存申请失败
31 }
32
33 void mSort(elementType A[], elementType tmpA[], int L, int rightEnd) {
34 if (L rightEnd) {
35 int center = (L + rightEnd) / 2;
36 mSort(A, tmpA, L, center);
37 mSort(A, tmpA, center + 1, rightEnd);
38 merge(A, tmpA, L, center + 1, rightEnd);
39 }
40 }
41
42 void merge(elementType A[], elementType tmpA[], int L, int R, int rightEnd) {
43 int tmpL = L,
44 leftEnd = R - 1,
45 elementNum = rightEnd - L + 1;
46 while (L rightEnd) {
47 if (A[L] A[R])
48 tmpA[tmpL++] = A[L++];
49 else
50 tmpA[tmpL++] = A[R++];
51 }
52 while (L leftEnd)
53 tmpA[tmpL++] = A[L++];
54 while (R rightEnd)
55 tmpA[tmpL++] = A[R++];
56 for (int i = 0; i )
57 A[rightEnd] = tmpA[rightEnd];
58 }
归并排序
标签：scanf 数列 free ges return mergesort efi malloc printf
原文地址：https://www.cnblogs.com/yinhao-ing/p/11128322.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
归并排序
文章链接：http://soscw.com/essay/30314.html
评论