基本原理：利用递归和分治的思想。原理见下图： 利用归并排序，对数组[10 4 6 3 8 2 5 7]进行排序(升序)。 
复杂度分析：分割的次数为logN,共有N个数，时间复杂度为(N*logN)。
代码实现(C)
#include <stdio.h> void mergearray(int a[], int first, int mid, int last, int temp[]) //将二个有序数列a[first...mid]和a[mid...last]合并//比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。{ 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]; //合并后的数列放在a[]中} void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; //将数列分割成二部分 mergesort(a, first, mid, temp); //递归分解数列：左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //依次将二个有序数列合并 } } int main(){ int a[] = {1,4,2,3,6,5,7,9,8,0}; int n = sizeof(a)/sizeof(a[0]); int b[n]; int i; mergesort(a,0,n-1,b); for(i=0; i<n; i++) { PRintf("%d ",a[i]); } return 0; }新闻热点
疑难解答
