今天继续找水题做巩固基础本领，1007又让我学到了新的东西，上篇文章说的如何用一个数组来连续储存随下标增加连续输入的多个字符串，1028题时候用了结构体实现，其实定义一个二维数组就可以了，1007题关键在后半部分的排序（把数组里面每个实数从小到大排出其所对应的下标。。）。AC代码:
#include<iostream>
using namespace std;
int main()
{int n,m,i,j,num,a[101],b[101],t,k;
char str[101][51],str1[51];
cin>>n>>m;
for(i=0;i<m;i++)
{cin>>str[i];
num=0;
for(j=0;j<n-1;j++)
for(k=j+1;k<n;k++)
if(str[i][j]>str[i][k])
num++;
a[i]=num;}
for(i=0;i<m;i++)
{ b[i]=0;
t=a[0];
for(j=1;j<m;j++)
if(t>a[j])
{t=a[j];
b[i]=j;}
a[b[i]]=1250;} //这里a[b[i]]=1250其实就是把一个足够大（大于 （1+..+49）就行了）的实数付给刚才选出最小的数组元素，使下次的选择不把它包括进来。
for(i=0;i<m;i++)
cout<<str[b[i]]<<endl;
return 0;}
而每次AC后去看别人AC的代码是我养成的习惯，以做到取长不短，这次果然又有所获，下面是我看到的多个AC代码中最优秀的一个：
#include <iostream>
#include <cstdlib>
using namespace std;
struct DNA{
string s;
int value;
};
int cmp(const DNA *a, const DNA *b) { return (a->value-b->value); }
int main()
{
int n,m;
while(cin>> m >>n)
{
DNA it[n];
for(int i=0;i!=n;i++)
{
cin >> it[i].s;
it[i].value = 0;
for(int j=0;j!=m;j++)
for(int k=j+1;k!=m;k++)
if(it[i].s[j]>it[i].s[k]) it[i].value++;
}
qsort(it,n,sizeof(DNA), (int (*)(const void *, const void *))cmp);
for(int i=0;i!=n;i++)
cout << it[i].s <<endl ;
}
return 0;
}
实在很优秀，用结构体包含其字符串和对应的inversions个数，从而用快排把inversions和其对应的字符串一次排出。真是优越无比。
这也是我初步认识快排函数和其实现方法。。。
所学到的:1,快排函数的定义和其实现的方法，用结构体可以一次把多项数据通通排出。。
2，刚开始在后半部分的排序实在花了很多时间，以后不要急着写完代码就抱着侥幸心理去测试AC不AC 要把自己代码的思路全理清，觉得没破绽了才放上去，要不不通过的话又要在调试上面花很多时间，有句话说得好，欲速则不达，切记。。。
这里为了加强对快排函数qsort格式的认识和理解，从百度上转来了qsort对7种类型数据的快排格式和一个实例：七种qsort排序方法
<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct In
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、计算几何中求凸包的cmp
int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}
PS:
其中的qsort函数包含在<stdlib.h>的头文件里，strcmp包含在<string.h>的头文件里
对浮点型快排实例:源程序, vc6通过的:
#include <stdio.h>
#include <stdlib.h>
int fcmp(const float*,const float*);
typedef int(*QSORT_UDF)(const void *,const void *);
int main()
{
float fArray[10] = {32.1,456.87,332.67,442.0,98.12,451.79,340.12,54.55,99.87,72.5};
qsort(fArray,10,sizeof(float),(QSORT_UDF)fcmp);
for(int i=0;i<10; i++)
printf(" %3.2f ",fArray[i]);
return 0;
}
int fcmp(const float *a,const float *b)
{
if( *a > *b )
return 1;
else if(*a < *b )
return -1;
return 0;
}