歸並操作(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語言實現如下： [cpp] #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; }
