算法学习笔记--归并排序

//时间复杂度O（nlg(n)）

void Merge(int a[],int p,int q,int r) {
    int n1 = q - p + 1,n2 = r - q,L[n1 + 1],R[n2 + 1];

    for (int i = 0; i < n1; i++)
        L[i] = a[p + i];
    for (int j = 0; j < n2; j++)
        R[j] = a[q + j+1];

    int i = 0, j = 0;
    for (int k = p; k < r+1; k++) {   //注意p ,r+1
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
    }


}


void MergeSort(int a[],int first,int last){ //first a 有效下标的第一个从0 开始，a中有效下标的下一个
  if(first<last){
      int q=(first+last)/2;
      MergeSort(a,first,q);//左边有序
      MergeSort(a,q+1,last);//右边有序
      Merge(a,first,q,last);//合并两边
  }

}
int main( )
{

int a[]={5,2,4,7,1,3,2,6};
MergeSort(a,0,7);
    for (int j = 0; j < 7; j++)
       cout<<a[j]<<endl;

    return 0;
}