给定两个有序数列，合并成一个新的升序数列

#include<bits/stdc++.h>
using namespace std;
int main(){
    const int SIZE = 100;
    int na,nb,a[SIZE],b[SIZE],i,j,k;
    cin >> na;
    for(i = 1 ; i <= na, i++){
        cin >> a[i];
    }
    cin >> nb;
    for(i = 1 ; i <= nb ,i++){
        cin >> b[i];
    }
    i = 1 ; 
    j = 1 ;
    while((i <= na) && (i < nb)){
        if(a[i] <= b[j]){
            cout << a[i ] << ' ';
            i++;
        }else{
            cout << b[j] << ' ';
            j++;
        }
    }
    if(i <= na){
        for(k = i ; k < na ; k++){
            cout << a[k]<< ' ';
        }
    }(i <= nb){
        for(k = j ; k < nb ; k++){
            cout << b[k]<< ' ';
        }
    }
    return 0;
}

归并排序

1. 算法介绍

归并排序是一种高效的 分治法（Divide and Conquer）排序算法，核心思想：

1️⃣ 分解：将数组递归拆分为最小单位（单个元素）

2️⃣ 合并：将有序子数组合并为更大有序数组

✅ 时间复杂度：最优/平均/最坏均为 O(n log n)

✅ 稳定性：稳定排序（相同元素顺序不变）

✅ 适用场景：大数据量、链表排序、外部排序

2. 分治思想图解

初始数组： [38, 27, 43, 3, 9, 82, 10]  
            ↓ 分解  
[38, 27, 43]      [3, 9, 82, 10]  
    ↓ 分解             ↓ 分解  
[38] [27, 43]    [3,9] [82,10]  
        ↓ 合并          ↓ 合并  
[27, 38, 43]      [3,9,10,82]  
            ↓ 合并  
     [3,9,10,27,38,43,82]

3. 合并操作详解

核心步骤：合并两个有序数组

Left数组: [27, 38, 43]   Right数组: [3, 9, 10, 82]  
Step1: 比较左首(27) vs 右首(3) → 取较小值 3  
Step2: 比较 27 vs 9 → 取 9  
Step3: 比较 27 vs 10 → 取 10  
Step4: 直接追加左数组：[27,38,43]  
结果：[3, 9, 10, 27, 38, 43, 82]

4. C++ 代码实现

#include<bits/stdc++.h>
using namespace std;
int arr[9] = {11,22,66,77,33,55,44,88};
int brr[9];
void merge(int l , int mid , int r){
    int i = l ; 
    int k = l;
    int j = mid + 1 ;
    while((i <= mid) && (j <=r)){
        if(arr[i] >arr[j]){
            brr[k++] = arr[i++];
        }else{
            brr[k++] = arr[j++];
        }
    }
    if(i <= mid){
        for(k = i ; k < mid ; k++){
            cout << arr[k]<< ' ';
        }
    }else{
        for(k = j ; k < r ; k++){
            cout << brr[k]<< ' ';
        }
    }
    while(i <= mid){
        brr[k++] = arr[i++];
    }
    while(j <= r){
        brr[k++] = arr[j++];
    }
    for (int i = l ; i <= r ; i ++){
        arr[i] = brr[i];
    }
}
void mergeSort(int l , int r){
    if(l >= r) return ;
    int mid = (l+r)/2;
    mergeSort(l,mid);
    mergeSort(mid+1 , r);
    merge(l,mid,r);
}
int main(){
    mergeSort(1,8);
    return 0;
}

5. 关键点分析

🔹 递归深度：共 log₂n 层分解

🔹 合并成本：每层合并需 O(n) 操作

🔹 空间复杂度：O(n)（临时数组开销）

🔹 优化策略：

小数组用插入排序减少递归开销
避免频繁内存分配（全局复用 temp 数组）

第四节