当前序列中,从后往前寻找第一对 相邻元素T[k-1]和T[k]
满足
T[k-1]<T[k]
;然后再从T[k]
开始找到最后一个元素且满足T[t]>T[k-1]
,然后二者交换;最后将T[k]
之后的元素包括T[k]
进行翻转;
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n , m ;
int w[N];
int main(){
cin >> n >> m ;
for(int i = 1; i <= n ; i ++) cin >> w[i];
while( m-- ){
int k = n;
while(w[k-1] >w[k]) k--;
int t = k;
while(w[t+1] > w[k-1]) t++;
swap(w[k-1],w[t]);
reverse(w+k,w+n+1);
}
for(int i = 1; i <= n;i ++) cout << w[i] << " ";
return 0;
}