合并排序

【合并排序】

【算法】

分治法的典型应用。对于一个需要排序的数组A[0..n-1]，先把它一分为二：A[0..[n/2]-1]和A[[n/2]..n-1]，对子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。

优点：最坏情况下时间复杂度为：nlogn -n+1

缺点：需要线性的额外空间。

【时间复杂度】

平均复杂度nlogn

【代码】

#include 
  
   
#include 
   
     void Merge(int a[], int left, int mid, int right, int tmp[]) { int i, j, k; i = left; j = mid + 1; k = 0; while(i <= mid && j <= right) { if(a[i] < a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while(i <= mid) tmp[k++] = a[i++]; while(j <= right) tmp[k++] = a[j++]; for(i = left, k = 0; i <= right; i++, k++) a[i] = tmp[k]; } void MergeSort(int a[], int left, int right, int tmp[]) { if(left < right) { int mid; mid = (left + right) / 2; MergeSort(a, left, mid, tmp);//左 MergeSort(a, mid + 1, right, tmp);//右 Merge(a, left, mid, right, tmp);//合并 } } int main(void) { int a[7] = {3, 5, 7, 8, 1, 9, 2}; int tmp[7]; MergeSort(a, 0, 6, tmp); for(int i = 0; i < 7; i++) printf("%d ", a[i]); return 0; }