#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
void getnext(char str[]){
    int l=strlen(str),i,j,k,temp;
    k=l-2;
    while(k>=0&&str[k]>str[k+1])k--;
    i=k+1;
    while(i<l&&str[i]>str[k])i++;
    temp=str[k];
    str[k]=str[i-1];
    str[i-1]=temp;
    for(i=l-1;i>k;i--){
        for(j=k+1;j<i;j++){
            if(str[j]>str[j+1]){
                temp=str[j];
                str[j]=str[j+1];
                str[j+1]=temp;
            }
        }
    }
}
int main(){
    char a[maxn];
    int n;
    cin>>a>>n;
    while(n>0){
        getnext(a);
        n--;
    }
    cout<<a<<endl;
    return 0;
}

回文串

#include<bits/stdc++.h>
using namespace std;
bool is_palindrome(string s){
    int len=s.size();
    bool flag=true;
    for(int i=0;i<len/2;i++){
        if(s[i]!=s[(len-1)-i]){
            flag=false;
        }
    }
    return flag;
}
int main(){
    string s2;
    cout<<is_palindrome(s2);
    return 0;
}

第一个出现一次的字符

#include<bits/stdc++.h>
using namespace std;
int arr[256];
int main(){
    string s;
    cin>>s;
    int len=s.size();
    for(int i=0;i<256;i++){
        arr[i]=0;
    }
    for(int i=0;i<len;i++){
        arr[s[i]]++;
    }
    for(int i=0;i<len;i++){
        if(arr[s[i]]==1){
            cout<<s[i];
            return 0;
        }
    }
    cout<<"no";
    return 0;
}

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

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

翻转数组

#include<bits/stdc++.h>
using namespace std;
int a[6];
int main(){
    left=0;
    right=5;
    while(left<right){
        swap(a[left],a[right]);
        left++;
        right--;
    }
    for(int i=0;i<5;i++){
        cout<<a[i];
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int arr[9] = {0,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++];
        }
    }
    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);    // 左数列 11,22,66,77
    mergeSort(mid+1,r);    // 右数列 33,55,44,88
    //... 合并
    merge(l,mid,r);
}
int main(){
    mergeSort(1,8);
    for(auto x : arr) cout << x << " ";
    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. 关键点分析

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

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

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

🔹 优化策略：

小数组用插入排序减少递归开销

避免频繁内存分配（全局复用 temp 数组）

5. 与快速排序对比

特性    归并排序    快速排序
最坏时间复杂度    O(n log n)    O(n²)
稳定性    ✅ 稳定    ❌ 不稳定
空间复杂度    O(n)    O(log n) 栈空间
适用场景    大数据量/外部排序    内存排序/随机数据

6. 可视化演示推荐

🔗 归并排序动画演示

（动态理解分解与合并过程）

总结：归并排序以 时间换空间，凭借稳定且可预测的性能，成为大规模数据排序的基石算法！