归并连接的思想与归并排序的思想类似，详见代码注释. ```C #include <stdio.h> #include <stdlib.h> #include <string.h> #include "merge_sort.h" /* array : 待处理的数组 low : 低位 middle : 中间位 high : 高位 */ void merge_array(int array[],int low,int middle,int high) { //左边数组的大小(middle在左边数组中,加1) int n1 = middle - low + 1; //右边数组的大小 int n2 = high - middle; //printf("---- merge_array : low = %d,high = %d,middle = %d.\n",low,high,middle); //初始化左右两边数组 int left[n1],right[n2]; for(int i = 0;i < n1;i++) left[i] = array[low+i]; for(int i = 0;i < n2;i++) right[i] = array[middle+i+1]; //归并 int i=0,j=0,k=low; //同时遍历左右两边数组,较小值进入到结果数组中(回填) for(;i < n1 && j < n2;) if(left[i] < right[j]) array[k++] = left[i++]; else array[k++] = right[j++]; //处理数组中剩余的其他元素 while(i < n1) array[k++] = left[i++]; while(j < n2) array[k++] = right[j++]; // printf("--- merge_array : ---\n"); // print_array(array+low,n1 + n2); } /* array : 待处理的数组 low : 低位 high : 高位 */ void merge_arraybyrange(int array[],int low,int high) { if (low >= high) return;//低位置大于等于高位值,退出 //取中间位置 int middle = (low + high)/2; //printf("---- merge_sort : low = %d,high = %d,middle = %d.\n",low,high,middle); //对左边数组进行排序 merge_arraybyrange(array,low,middle); //对右边数组进行排序 merge_arraybyrange(array,middle+1,high); //两边数组排序完毕后,归并两边的数组 merge_array(array,low,middle,high); // printf("--- merge_sort : ----\n"); // print_array(array+low,high - low + 1); } /* 递归调用方法 array : 待处理的数组 low : 低位 high : 高位 */ void merge_sort_recursion(array *tmparr) { int low = 0; int high = tmparr->counter - 1; merge_arraybyrange(tmparr->arr,low,high); } /* 非递归调用方法 a/b:已完成排序的数组 c:结果数组 */ void merge_twoarrays2one(array *a,array *b,array *c) { int i=0,j=0; c->counter=-1; for(;i < a->counter && j < b->counter;) { //归并排序,任意一个数组结束则循环结束 if(a->arr[i] < b->arr[j]) { c->arr[++c->counter] = a->arr[i++]; } else { c->arr[++c->counter] = b->arr[j++]; } } //处理余下的数据 while(i < a->counter) { c->arr[++c->counter] = a->arr[i++]; } while(j < b->counter) { c->arr[++c->counter] = b->arr[j++]; } //从0开始计数,counter+1 c->counter++; } /* tmparr : 待排序的array结构体 */ void merge_sort(array *tmparr) { //临时数组 int tmp[tmparr->counter]; //临时数组（缓存） array buffer; buffer.arr = tmp; for(int i=1;i < tmparr->counter;i=i*2) { //i=每次比较的数量=2^x = 1/2/4/8... for(int j=0;j < tmparr->counter;j+=i*2) { //j=比较起始位置,每次比较i个数 if(j+i >= tmparr->counter) break; array arr1,arr2; //指向比较的位置(数组1) arr1.arr = tmparr->arr+j; arr1.counter = i; //指向比较的位置(数组2) arr2.arr = tmparr->arr+j+i; arr2.counter = i; //数组2的数量,判断以免越界 if(j+i*2 >= tmparr->counter) arr2.counter = tmparr->counter - (j + i); //归并数组1&2 merge_twoarrays2one(&arr1,&arr2,&buffer); // printf("---------- i = %d,j = %d,counter = %d\n",i,j,buffer.counter); // print_array(buffer.arr,buffer.counter); //归并好的数据拷贝到tmparr中 memcpy(tmparr->arr+j,buffer.arr,buffer.counter*sizeof(int)); } // printf("------------ i = %d\n",i); // print_array(tmparr->arr,tmparr->counter); } } ``` 运行输出 ```bash ethanhe@DESKTOP-V73MH70 /d/yunpan/work/Z-SRC/sort $ /d/tmp/test.exe --------- test_merge ----------- item[0] is 1 item[1] is 5 item[2] is 10 item[3] is 21 item[4] is 30 item[5] is 40 item[6] is 99 item[7] is 100 item[8] is 200 item[9] is 301 item[10] is 400 --------- test_merge by recursion----------- item[0] is 1 item[1] is 5 item[2] is 10 item[3] is 21 item[4] is 30 item[5] is 40 item[6] is 99 item[7] is 100 item[8] is 200 item[9] is 301 item[10] is 400 ```