数据结构-归并排序-自顶向下

BottomUpSort归并排序，是自底向上的排序

下面介绍一个自顶向下的排序

MergeSort排序，也是一个分治的典例。在这之前还要学习一下合并两个已排序的表，在BottomUpSort那一篇里面有写

                                9 4 5 2 1 7 4 6

                                1 2 4 4 5 6 7 9 

                         1/14                         15\28

               9 4 5 2                                           1 7 4 6

               2 4 5 9                                           1 4 6 7

         2 /7           8\13                          16 /21      22\27     

     9 4                    5 2                       1 7                     4 6

     4 9                    2 5                       1 7                     4 6

3 /4  5 \ 6      9/10  11\12    17/18  19\20   23/24   25 \26

 9         4          5             2          1             7          4              6 

 9         4          5             2          1             7          4              6

输入：n个元素的数组A[ 1...n ]

输出：按非降序排列的数组A [ 1..n ]

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=30; void Merge(int *a,int p,int q,int r){ int s=p,t=q+1;//s:p~q t:q+1~r int b[N],k=p;//b数组下标k:p~r while(s<=q && t<=r){ if(a[s]<=a[t]){ b[k]=a[s]; s++; }else { b[k]=a[t]; t++; } k++; } if(s == q+1) {//前一半结束 for(int i=t;i<=r;i++) b[k++]=a[i]; }else { for(int i=s;i<=r;i++) b[k++]=a[i]; } for(int i=p;i<=r;i++) a[i]=b[i]; } void mergeSort(int *a,int low,int high){ if(low<high){ int mid=(low+high)/2; mergeSort(a,low,mid); mergeSort(a,mid+1,high); Merge(a,low,mid,high); } } int main() { int a[N]={0,9,4,5,2,1,7,4,6}; int len=8; mergeSort(a,1,len); for(int i=1;i<=len;i++){ printf("%d ",a[i]); } return 0; }