思路：打算用一个结构体来存储，含有一个string来存储字符串，含有一个int来存储inversions数；然后根据inversions来排序，再输出。找到在stdlib中有个函数为qsort，实现了快速排序，为了添加稳定性，在结构体里添加了一个int来存储序号，当两个数的inversions一样的时候，按照序号来排序。
tips：
qsort(s,n,sizeof(s[0]),cmp);
其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]
这样的表达式）
第二个参数是参与排序的元素个数;
第三个参数是单个元素的大小,推荐使用sizeof(s[0])这样的表达式
第四个参数是比较函数，要自己编写
典型的cmp的定义是int cmp(const void *a,const void *b);返回值必须是int,两个参数的类型必须都是const void *,那个a,b是我随便写的,个人喜好.
假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回
0,其他的依次类推
在函数体内要对a,b进行强制类型转换后才能得到正确的返回值,不同的类型有不同的处理
方法
** 关于快排的一些小问题 **
1.快排是不稳定的,这个不稳定一个表现在其使用的时间是不确定的,最好情况(O(n))和最
坏情况(O(n^2))差距太大,我们一般说的O(nlog(n))都是指的是其平均时间.
2.快排是不稳定的,这个不稳定表现在如果相同的比较元素,可能顺序不一样,假设我们有
这样一个序列,3,3,3,但是这三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定
就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.6的例子就
是说明这个问题的)
3.快排的比较函数的两个参数必须都是const void *的
4.快排qsort的第三个参数,那个sizeof,推荐是使用sizeof(s[0])这样,特别是对结构体,
往往自己定义2*sizeof(int)这样的会出问题,用sizeof(s[0)既方便又保险
Source Code
| Problem: 1007 | User: yuanting0505 | |
| Memory: 236K | Time: 32MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <iostream> #include <stdlib.h> #include <string> using namespace std; structNode { string s;//储存字符串 int no;//序号，来保持快排的稳定性 int inversions;//记录unsorted 数，依据这个来排序 }; structNode node[100]; //qsort中的com函数 int cmp(const void *a,const void *b) { structNode *aa=(Node *)a; structNode *bb=(Node *)b; if(aa->inversions!=bb->inversions) { return((aa->inversions>bb->inversions)?1:-1); } else//相等时按照原序 { return((aa->no>bb->no)?1:-1); } } int main(int argc, const char * argv[]) { int n,m; cin>>n>>m;//n：字符串长度，m：字符串数 for(int i=0;i<m;i++) { cin>>node[i].s; node[i].no=i; //计算inversions数 int in=0; for(int j=0;j<n;j++) { for(int k=j+1;k<n;k++) { if(node[i].s[j]>node[i].s[k]) { in++; } } } node[i].inversions=in; } //使用库里的qsort函数 qsort(node,m,sizeof(node[0]),cmp); //输出 for(int i=0;i<m;i++) { cout<<node[i].s<<endl; } return 0; }