冒泡排序和快速排序都是基于"交换"进行的排序方法，你的任务是对题目给定的N个（长整型范围内的）整数从小到大排序，输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。
连续多组输入数据，每组数据第一行给出正整数N(N ≤ 10^5)，随后给出N个整数，数字间以空格分隔。
输出数据占一行，代表冒泡排序和快速排序进行排序分别需要的交换次数，数字间以1个空格分隔，行末不得有多余空格。
注意：数据相等时不做交换
///Accode
#include <bits/stdc++.h> using namespace std; const int maxn=100010; int num[maxn],num2[maxn]; int Bub; int Qsort; int n; void Bubsort() { int i,j,t; for(i=2; i<=n+1; i++) /// MAX i=n+1 不会RE 控制循环 { for(j=1; j<=n+1-i; j++) ///下标从一开始 j最大范围大于1小于n-1 { if(num[j]>num[j+1]) { t=num[j]; num[j]=num[j+1]; num[j+1]=t; Bub++; ///一旦交换 +1; } } } } void quicksort(int l,int r) { if (l>=r) return; ///l==r的时候 只剩一个元素了 So不用quicksort了 int i=l; int j=r; int x=num2[i]; while (i<j) ///↑↑↑ 所以这里用了 i < j; { while (i<j&&num2[j]>=x) ///从小到大排序 右边的大于x , j--; { j--; } if (num2[i]!=num2[j]) ///等于的时候交换次数不计 { Qsort++; } num2[i]=num2[j]; while (i<j&&num2[i]<=x) { i++; } if (num2[j]!=num2[i]) { Qsort++; } num2[j]=num2[i]; } num2[i]=x; ///num2[i] 回归原数据 quicksort(l,i-1); ///递归左 quicksort(i+1,r); ///递归右半边 } int main() { int i,key; while (cin>>n) { Bub=0; Qsort=0; for (i=1; i<=n; i++) ///用了两个数组存起来了..... { cin>>key; num[i]=key; num2[i]=key; } Bubsort(); quicksort(1,n); cout<<Bub<<" "<<Qsort<<endl; } return 0; } ///突然发现 老用STL用的排序不太会写了.....所以有时间还会附图更新....