赞
踩
归并排序是建立在归并操作上的一种有效的算法,该算法是采用分治法的一个非常典型的应用,
是一种稳定的排序算法。
将已有的子序列合并,得到完全有序的的序列;即先使每个子序列有序,再使子序列段间有序。
若将两个有序表合并成一个有序表,成为二路归并。
代码实现如下:
- #include "stdio.h"
- #include "malloc.h"
- #include "string.h"
-
- void PrintfArray(int* ar, int left,int right)
- {
- for (int i = left; i < right; i++)
- printf("%d ", ar[i]);
- }
-
- void _MergeSort(int* ar, int left, int right,int *tmp)
- {
- if (left >= right)
- return;
- int mid = (right + left) / 2;
- _MergeSort(ar, left, mid, tmp);
- _MergeSort(ar, mid + 1, right, tmp);
-
- int begin1 = left, end1 = mid;
- int begin2 = mid + 1, end2 = right;
- int k = left;
- while (begin1 <= end1 && begin2 <= end2)
- {
- if (ar[begin1] < ar[begin2])
- tmp[k++] = ar[begin1++];
- else
- tmp[k++] = ar[begin2++];
- }
- while (begin1 <= end1)
- tmp[k++] = ar[begin1++];
- while (begin2 <= end2)
- tmp[k++] = ar[begin2++];
- memcpy(ar + left, tmp + left, sizeof(int)*(right - left + 1));
-
- }
-
- void MergeSort(int* ar, int left, int right)
- {
- int n = right - left;
- int* tmp = (int*)malloc(sizeof(int)*n);
- _MergeSort(ar, left, right - 1, tmp);
- free(tmp);
- tmp = NULL;
-
- }
-
- int main()
- {
- int ar[] = {13,37,34,78,90,88,12 };
- int n = sizeof(ar) / sizeof(ar[0]);
- PrintfArray(ar, 0, n);
- MergeSort(ar,0,n);
- printf("\n");
- PrintfArray(ar, 0, n);
- }
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。