NO IMAGE

我自己的思路,順便複習快排

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int getcount(string s,int len){//求逆序數
int count=0;
for(int i=1;i<len;  i){
for(int j=0;j<i;  j){
if(s[j]>s[i]){
count;
}
}
}
return count;
}
int quicksort(vector<int>& t,int low,int high,vector<int>& o){
int pivot=t[low],pivot_o=o[low];
while(low<high){
while(pivot<=t[high]&&low<high) --high;
t[low]=t[high];
o[low]=o[high];
while(t[low]<=pivot&&low<high)   low;
t[high]=t[low];
o[high]=o[low];
}
t[low]=pivot;
o[low]=pivot_o;
return low;
}
void qsort(vector<int>& t,int low,int high,vector<int>& o){
if(low>=high) return;
int mid=quicksort(t,low,high,o);
qsort(t,low,mid-1,o);
qsort(t,mid 1,high,o);
}
int main(){
int m,n;
cin>>m>>n;
vector<string> vstr;
vector<int> count;
vector<int> order;
string s;
for(int i=0;i<n;  i){
cin>>s;
vstr.push_back(s);
count.push_back(getcount(s,m));
order.push_back(i);
}
qsort(count,0,n-1,order);
for(int i=0;i<n;  i){
cout<<vstr[order[i]]<<endl;
}
return 0;
}

求逆序數我用了傻辦法,看看人家的方法->點我

int InversionNumber(char* s,int len)
{
int ans=0;  //s逆序數
int A,C,G;  //各個字母出現次數,T是最大的,無需計算T出現次數
A=C=G=0;
for(int i=len-1;i>=0;i--)
{
switch(s[i])
{
case 'A':A  ;break;  //A是最小的,無逆序數
case 'C':
{
C  ;
ans =A;  //當前C後面出現A的次數就是這個C的逆序數
break;
}
case 'G':
{
G  ;
ans =A;
ans =C;
break;
}
case 'T':
{
ans =A;
ans =C;
ans =G;
break;
}
}
}
return ans;
} 

qsort也是可以呼叫滴,記得#include<algorithm> 嗯。