当前位置:编程学习 > C/C++ >>

poj1007 qsort快排

这道题比较简单,但通过这个题我学会了使用c++内置的qsort函数用法,收获还是很大的!
首先简要介绍一下qsort函数。
 
1、它是快速排序,所以就是不稳定的。(不稳定意思就是张三、李四成绩都是90,张三成绩在前;排序完毕后有可能变成李四的90在前,张三在后)
 
2、需要包含头文件:cstdlib
 
3、原型:void qsort(void *base,int nelem,int width,int(*fcmp)(const void*,const void *));
 
 4、参数:数组首地址,数组内元素数量,每个元素占用空间大小,指向函数的指针
 
这道题意思是给出一个字符串,从该字符串首字母开始判断在其右边有多少个字母比他小,直到判断玩整个序列得出这个字符串的一个value。如“BAAED”,B比右侧的A(2个)大,E比D大,所以最后这条的value就是3。然后输入若干条字符串,按照value最低到高排序后输出,如果value相同则按输入的顺序输出。
这时可能会想既然value相同时要按输入的顺序输出,那么快速排序肯定就是不行的了,因为它不稳定嘛。这就是这个题一个比较巧妙的地方,我把字符串的value值乘以1000后再加上该字符串是第几个输入进来的i,构成排序时所比较的数字num[]。因为题目规定最多输入100条字符串,所以value大的串势必num要大,即使value相同的串,先输入的串的i要小,所以其num也就要小,这么一来既把字符串与它的value绑定,又避免出现相同数字比较大小的情况,所以快排就一点问题都没有啦!
 
/** 
  *poj1007 
  *@author monkeyduck 
  *@2013.9.21 
  */  
#include<iostream>  
#include<cstdlib>  
using namespace std;  
char str[110][55];  
int num[100];  
int cmp(const void* a,const void* b)  
{  
    return *(int*)a-*(int*)b;  
}  
int main()  
{  
    int n,m;  
    cin>>n>>m;  
    for (int i=0;i<m;i++)  
    {  
        cin>>str[i];  
        int count=0;  
        for (int j=0;j<n-1;j++)  
        {  
            for (int k=j+1;k<n;k++)  
            {  
                if (str[i][j]>str[i][k]) count++;  
            }  
        }  
        num[i]=count*1000+i;  
    }  
    qsort(num,m,sizeof(num[0]),cmp);  
    for (int q=0;q<m;q++)  
    {  
        cout<<str[num[q]%1000]<<endl;  
    }  
    return 0;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,