编译环境：gcc4.4.3
#include <stdio.h> #define MAX 10 void prtarry(int* sum, int n); //p, q, r均为数组下标 void merge(int *A, int p, int q, int r) { printf("p=%d q=%d r=%d ", p, q, r); int i, j, k; int n1 = q - p + 1; int n2 = r - q; int L[MAX], R[MAX]; for (i = 0; i < n1; i++) L[i] = A[p + i]; for (j = 0; j < n2; j++) R[j] = A[q + j + 1]; /* * 哨兵牌 *L[n1] = 99999; *R[n2] = 99999; */ i = 0; j = 0; for (k = p; k <= r; k++) { //如果其中一侧的元素复制完了，那么剩下的另一侧元素无需比较，直接复制即可 //这样做是必须的，因为一侧元素复制完后，它的指针指向的元素就是一个未知数（访问越界） //另一种方法是使用哨兵牌，在每一侧末尾放置一个无限大的数。 if (i >= n1) { A[k] = R[j++]; continue; } else if (j >= n2) { A[k] = L[i++]; continue; } if (L[i] <= R[j]) { A[k] = L[i]; i++; } else { A[k] = R[j]; j++; } } prtarry(A, r+1); } void merge_sort(int *A, int p, int r) { int q; if (p < r) { //q = (p + r) / 2; //p + r有可能会溢出 //q = p/2 + r/2; //两次除法会导致精度成倍降低，导致计算结果错误。例如5/2+3/2=3, (5+3)/2=4 q = ((p & r) + ((p ^ r) >> 1)); //原理是？ merge_sort(A, p, q); merge_sort(A, q+1, r); merge(A, p, q, r); } } void prtarry(int* sum, int n) { int i; printf("array: "); for(i=0; i<n; i++) { printf("%2d ", sum[i]); } printf("\n"); } int main(int argc, const char *argv[]) { int sum[MAX] = {5,7,8,2,4,6,9,0,1,3}; prtarry(sum, MAX); merge_sort(sum, 0, MAX-1); prtarry(sum, MAX); return 0; }转载于:https://www.cnblogs.com/tonykong/archive/2013/02/05/merge_sort.html
相关资源：归并排序 C语言实现