排序

归并排序和基数排序

nkul · 7月9日 · 2020年 · 222次已读

归并排序

归并排序,最重要的过程是合并。合并的过程是对2个有序数组排序成一个数组。

合并过程

/**
 * @param a  原数组
 * @param b  在原数组做修改,因此要辅助数组记录原来"两个有序数组"
 * @param l  第一个有序数组左边界
 * @param mid 第一个数组右边界
 * @param r  第二个数组右边界
 * 两个数组分别为a[l,mid],a[mid+1,r]
 */
void merge(int a[],int b[],int l,int mid,int r){
    //备份,防止更改
    for(int i=l;i<=r;i++){
        b[i] = a[i];
    }
    // i,j两个指针分别指向原来两个有序数组的头,k指向新数组
    int i=l,j=mid+1,k=i;
    for(;i<=mid && j<=r;k++){
        if(b[i]<=b[j]) a[k] = b[i++];
        else a[k] = b[j++];
    }
    while (i<=mid) a[k++] = b[i++];
    while(j<=r) a[k++] = b[j++];
}

合并排序

void merge_sort(int a[],int l,int r){
    int b[r-l+1];
    if(l

性质

  • 内部排序
  • 稳定
  • 空间复杂度:o(n)
  • 时间复杂度:o(nlgn)


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!