排序之归并操作
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。 如 设有数列{6，202，100，301，38，8，1} 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4
总计： 11次
c语言实现如下：
#include <stdio.h>#include <string.h>#include <malloc.h>void display(int array[],int size){ printf("the array is:"); int i; for(i=0;i<size;i++){ printf("%d ",array[i]); } printf("\n");}//将a数组中first开始mid结束的数组，mid+1开始last结束的数组 进行合并，再存放回a中void mergearray(int a[], int first, int mid, int last, int temp[]){ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i];}void sort(int a[], int first, int last, int temp[]){ if (first < last) { int mid = (first + last) / 2;//左侧的数组进行排序 sort(a, first, mid, temp);//右侧的数组进行排序 sort(a, mid + 1, last, temp);//将左右数组进行合并 mergearray(a, first, mid, last, temp); }}int main(void){ int array[10]={34,45,1,39,21,68,65,100,4,51}; display(array,10);//申请临时数组，用于存放合并的数组 int* temp = (int *)malloc(sizeof(int)*10); memset(temp,0,10);//归并算法函数 sort(array,0,10-1,temp);free(temp);temp = null; display(array,10); return 0;}