# include<iostream> using namespace std; const int N=1e4; int arr[N],n; //录入数组a void input_arr(int n,int a[]){ for(int i=1;i<=n;i++){ cin>>a[i]; } } //输出排序后的数组 void print_arr(int n,int a[]){ for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } cout<<endl; } //对数组进行冒泡排序 int cnt=0,cnt2=0;//cnt:交换了几次，cnt2:比较了几次 void sort_1(int n, int a[]){ for(int i=1;i<=n-1;i++){//进行n轮的扫描 bool k=false;//优化冒泡排序，如果序列已经有序就结束排序了 //将剩余无序数组进行排序, for(int j=1;j<=n-i;j++){//上升法：j<=n-i代表每轮比完剩余的无序数组 //下降法，每轮排序之后前面的位置有序j=n-1;j>=i;j-- cnt2++; if(a[j]>a[j+1]) {swap(a[j],a[j+1]);cnt++;k=true;} } print_arr(n,a); //if(k==false) break;//结束排序 } } //逆序对的概念：在一个序列中，如果位置i和j以及存在i,j上的元素存在下面关系， //则认为是一对逆序对：i<j,且A[i]>A[j],则称(A[i], A[j])为数组A中的一个逆序对。 int main(){ cin>>n; input_arr(n,arr);//输入n个数字，存入数组arr：1-n的位置 sort_1(n,arr);//对数组前n位进行排序 //print_arr(n,arr);//输出数组arr：1-n的位置 //cout<<cnt<<endl<<cnt2<<endl; return 0; }