qsort的用法(一)

by admin on 2020年1月28日

本文章摘要自

qsort(卡塔尔  应该正是用的快排。貌似是以数据块的方法移动多少,速度不慢。

qsort函数、sort函数 (细心收拾篇卡塔尔国

如有版权难题,请与自个儿交流!谢谢

原型:
_CRTIMP void __cdecl qsort (void*, size_t, size_t,int (*)(const
void*, const void*));

先证实一下qsort和sort,只可以对接连几日内存的多寡开展排序,像链表那样的构造是敬敏不谢排序的。

众多个人问那一个东西.小编早前也看了悠久,明日翻到从前学快排的时候写的演习code,基本上
能隐讳绝半数以上用法了.

释疑:    qsort ( 数组名 ,成分个数,成分占用的半空中(sizeofState of Qatar,比较函数卡塔尔国
正如函数是四个投机写的函数  信守 int com(const void *a,const void *b)
的格式。
当a b关系为 >  <  = 时,分别重临正值 负值 零 (大概相反)。
接收a b 时要强逼转变类型,从void * 转变回应该的体系后,实行操作。
数组下标从零最初,个数为N, 下标0-(n-1卡塔尔国。

首先说一下, qsort

个中有超多地方没看清相等的情景,按道理来讲非常意况下应当再次回到0的,这几个请看代码的
时候注意.笔者尽大概确定保障代码不出错了.

示例:
int nn[100],n=100;
int com(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}   

qsort(基本火速排序的秘籍,每一趟把数组分成两片段和中等的三个分开值,而对于有四个重复值的数组来说,基本连忙排序的频率相当低,且动荡)。集成在C语言库函数里面包车型客车的qsort函数,使用

路划分的不二秘诀消除排序那几个标题。所谓三路划分,是指把数组划分成小于划分值,等于划分值和过量划分值的八个部分。

下边的那个验证和主题材料都是私家原创,没查什么材料,所以不有限援助其完全科学,在这里表示个
人狼狈现身的难点负任何义务,我们WA了依然干什么的绝不怪作者,可是起码如今来讲本人用起来
是没难题的 :卡塔尔国

qsort((void *)nn,n,sizeof(int),com);
相关:
为什麽你一定要予以成分个数?(因为阵列不清楚它协和有稍许个成分)为什麽你不得不予以
double 的尺寸?(因为 qsort 不知底它要排序的单位是
doubles.)为什麽你不得不写那多少个丑陋的、用来相比 doubles 数值的函式?(因为
qsort 供给一个目的指向有个别函式,因为它不知晓它所要排序的成分型别)为什麽
qsort 所运用的比较函式接纳的是 const void* 引数并非 char*
引数?(因为 qsort 能够对非字串的数值排序)Bjarne Stroustrup

 

/*—————————————————————————-*/

 

具体介绍:-^^

** 关于快排函数的有的表达 **

 

void qsort( void *base, size_t num, size_t width, int (__cdecl
*compare )

qsort,包涵在stdlib.h头文件里,函数意气风发共八个参数,没回来值.三个独立的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);

int compare (const void *elem1, const void *elem2 ) );

qsort(s,n,sizeof(s[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);

 

当中第多个参数是参加排序的数组名(可能也得以精晓成最早排序的地址,因为能够写&s[i]
如此的表明式,那些主题材料上面有证实卡塔尔; 第3个参数是参加排序的要素个数;
第三个三数是
单个成分的深浅,推荐使用sizeof(s[0]State of Qatar那样的表明式,上边也许有认证 :卡塔尔(قطر‎;第两个参数正是
众几人认为非常纳闷的可比函数啦,关于这一个函数,还要说的可比麻烦…

三、对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);

qsort(即,quicksort)主要依照你给的相比规范给二个高效排序,首假若因此指针移动完结排序功用。排序之后的结果仍旧位居原本数组中。

大家来谈谈cmp这一个比较函数(写成cmp是自个儿的私家爱好,你能够不管写成怎么着,譬喻qcmp什么
的卡塔尔(قطر‎.标准的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);

参数意义如下:

int cmp(const void *a,const void *b);

五、对构造体二级排序
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);

先是个参数 base 是
须要排序的对象数组名(也许也得以清楚成开头排序的地址,因为能够写&s[i]如此的表明式)

重回值必得是int,多少个参数的等级次序必得皆以const void
*,这些a,b是本身任由写的,个人喜好.
假定是对int排序的话,要是是升序,那么便是只要a比b大重回八个正在,小则负值,相等重回
0,别的的依次类推,前边有例子来评释对两样的门类怎么着进展排序.

六、对字符串进行排序
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);

其次个参数 num 是 参加排序的对象数组成分个数

在函数体内要对a,b进行强制类型调换后技艺博取准确的重返值,差异的档案的次序有例外的管理
方法.具体情形请参谋前边的例子.

团结写一个纯字符串的:(temp是二维的字符串数组,j是一同需排序的字符串个数State of Qatar

其七个参数 width
是单个成分的深浅(只怕指标数组中每贰个因素长度),推荐应用sizeof(s[0])那样的表明式

/*—————————————————————————-*/

int cmpstr(const void *a,const void *b)
{
   return strcmp((char*)a,(char*)b);
}

第四个参数 compare 正是让广大人认为分外纳闷的可比函数啦。

** 关于快排的片段小标题 **

    qsort(temp, j,sizeof(temp[0]),cmpstr);

 

1.快排是不安宁的,那么些不安宁三个表以后其采用的光阴是不明确的,最佳状态(O(nState of Qatar卡塔尔国和最
坏情形(O(n^2State of Qatar卡塔尔差别太大,大家日常说的O(nlog(n卡塔尔国State of Qatar都是指的是其平均时间.

七、总括几何中求凸包的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卡塔尔State of Qatar//借使在一条直线上,则把远的放在前方
return 1;
else return -1;
}

咱们来总结商讨compare这么些相比较函数(写成compare是本身的村办中意,你能够不管写成什么,举例cmp 什么的,在背后我会一向用cmp做表达)。

2.快排是不安静的,那几个不安静表现在尽管相通的相比较成分,大概顺序不均等,假若大家有
如此那般一个行列,3,3,3,可是那七个3是有分其他,大家标记为3a,3b,3c,快排后的结果不必然
哪怕3a,3b,3c那样的排列,所以在好几特定场地我们要用构造体来使其安居(No.6的例证就
是表明那么些难题的卡塔尔国

qsort(State of Qatar是c程序库stdlib.h中的二个函数,必要相比较函数完结排序;
sort(卡塔尔国是STL中的规范算法。
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *((int *)b)-*((int *)a);
}
    .
    .
     .
qsort(q,n,sizeof(int),cmp);
    .
    .
    .
}
qsort对意气风发维数组和字符串数组的排序:
#include “stdio.h”
#include “stdlib.h”
int a[100];
int cmp(const void *p,const void *q)
{
    return (*(int*)p)-*((int*)q);
}
int main()
{
    int n;
    scanf(“%d”,&n);
    for(int i=0;i<n;i++)
        scanf(“%d”,&a[i]);
    qsort((void*)a,n,sizeof(a[0]),cmp);
    for(int i=0;i<n;i++)
      printf(“%dn”,a[i]);
    //while(1);
    
int cmp(const void *p,const void *q)
{
    return strcmp((char*)p,(char*)q);
}
int main()return 0;
}

 

3.快排的可比函数的八个参数必须都以const void
*的,这几个要特别注意,写a和b只是自己的
民用爱好,写成cmp也只是自家的村办喜好.推荐在cmp里面重新定义多个指针来勉强类型调换,
特别是在对构造体进行排序的时候

#include “stdio.h”
#include “stdlib.h”
#include “string.h”
char a[20005][25];
{
    int n,m,i,j;
    while(1)
    {
            scanf(“%d%d”,&n,&m);
            if(n==0&&m==0) break;
            for(i=0;i<n;i++)
            {
               scanf(“%s”,a[i]);
            }
            qsort((void*)a,n,sizeof(a[0]),cmp);
            for(i=0;i<n;i++)
               printf(“%sn”,a[i]);
    }
}

优秀的compare的概念是int compare(const void *a,const void *b);

4.快排qsort的第多少个参数,那么些sizeof,推荐是接收sizeof(s[0]State of Qatar那样,特别是对布局体,
再三本身定义2*sizeof(int卡塔尔那样的会出难点,用sizeof(s[0State of Qatar既有益又确认保障

 

重临值必须是int,四个参数的项目必得都以const void
*,那一个a,b是不管写的,个人喜好。假若是对int排序的话,要是是升序,那么正是只要a比b大返回多个正值,小则负值,相等重返0,其余的依次类推,前边有例子来证实对两样的品种怎么着实行排序。

5.假设要对数组举香港行政局部排序,譬喻对三个s[n]的数组排列其从s[i]开始的m个元素,只需要
在第多少个和第一个参数上进展部分改变:qsort(&s[i],m,sizeof(s[i]),cmp);

 

/*—————————————————————————-*/

 

** 标程,比方表明 **

qsort 的使用格局:

No.1.手工业达成QuickSort
#include <stdio.h>

风华正茂、对int类型数组排序

int a[100],n,temp;

int num[100];

void QuickSort(int h,int t)
{
     if(h>=t) return;
     int mid=(h+t)/2,i=h,j=t,x;
     x=a[mid];
     while(1)
     {
         while(a[i]<x) i++;
         while(a[j]>x) j–;
         if(i>=j) break;
         temp=a[i];
         a[i]=a[j];
         a[j]=temp;
     }
     a[mid]=a[j];
     a[j]=x;
     QuickSort(h,j-1);
     QuickSort(j+1,t);
     return;
}

int cmp ( const void *a , const void *b )

int main()
{
     int i;
     scanf(“%d”,&n);
     for(i=0;i<n;i++) scanf(“%d”,&a[i]);
     QuickSort(0,n-1);
     for(i=0;i<n;i++) printf(“%d “,a[i]);

{

     return(0);
}

  return *(int *)a – *(int *State of Qatarb;  //升序排序

No.2.最布满的,对int数组排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//return *(int *)b – *(int *State of Qatara; //降序排序

int s[10000],n,i;

/*足见:参数列表是多个空指针,以后她要去指向您的数组成分。所以转型为您日前的种类,然后取值。

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

       
升序排列时,若首先个参数指针指向的“值”大于第4个参数指针指向的“值”,则赶回正;若首先个参数指针指向的“值”等于第三个参数指针指向的“值”,则赶回零;若首先个参数指针指向的“值”小于第一个参数指针指向的“值”,则赶回负。

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++) scanf(“%d”,&s[i]);
    
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf(“%d “,s[i]);
    
     return(0);
}

        降序排列时,则恰恰相反。

No.3.对double型数组排序,原理同int

*/

此处做个注释,本来是因为要推断假诺a==b重返0的,但是严刻来说,五个double数是不容许特别的,只好说fabs(a-b卡塔尔国<1e-20之类的这么来判别,所以这里只回去了1和-1
#include <stdio.h>
#include <stdlib.h>

}

double s[1000];
int i,n;

qsort(s,n,sizeof(s[0]),cmp);

int cmp(const void * a, const void * b)
{
     return((*(double*)a-*(double*)b>0)?1:-1);
}

 

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++) scanf(“%lf”,&s[i]);
    
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf(“%lf “,s[i]);
    
     return(0);
}

演示完整函数(已在 VC6.0上运营通过):

No.4.对三个字符数组排序.原理同int
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int s[10000],n,i;
int cmp(const void *a,const void *b)
{
return(*(int *)b-*(int *卡塔尔国aState of Qatar;  //完毕的是降序排序
}
int main()
{

char s[10000],i,n;

// 输入想要输入的数的个数
scanf(“%d”,&n);
for(i=0;i<n;i++)
scanf(“%d”,&s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf(“%d “,s[i]);
return(0);
}

int cmp(const void *a,const void *b)
{0
     return(*(char *)a-*(char *)b);
}

  

int main()
{
     scanf(“%s”,s);
     n=strlen(s);
     qsort(s,n,sizeof(s[0]),cmp);
    
     printf(“%s”,s);
     return(0);
}

二、对char类型数组排序(同int类型)

No.5.对布局体排序

char word[100];

注脚一下.众多时候我们都会对构造体排序,举个例子校赛预选赛的特别樱花,经常那时都在
cmp函数里面先强制调换了项目,不要在return里面转,作者也说不清为何,可是那样程序会
更清楚,何况相对是对的的. 这里相近请留神double重回0的难点

int cmp( const void *a , const void *b )

#include <stdio.h>
#include <stdlib.h>

{

struct node
{
     double date1;
     int no;
} s[100];

//注意,网络海人民广播电视台湾大学学本科子是 “ return *(char *)a – *(int *)b;  ” 

int i,n;

//因为审核人的不细心,盲目copy,以其昏昏招人昭昭,传的直白是错的 *(int *)b

int cmp(const void *a,const void *b)
{
     struct node *aa=(node *)a;
     struct node *bb=(node *)b;
     return(((aa->date1)>(bb->date1))?1:-1);
}

//应该是return *(char *)a – *(char *)b;

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++)
     {
         s[i].no=i+1;
         scanf(“%lf”,&s[i].date1);
     }
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf(“%d   %lfn”,s[i].no,s[i].date1);
    
     return(0);
}

return *(char *)a – *(char *)b;

No.6.对布局体排序.参预no来使其安静(即data值相等的情景下按原本的逐个排State of Qatar

}

#include <stdio.h>
#include <stdlib.h>

qsort(word,100,sizeof(word[0]),cmp);

struct node
{
     double date1;
     int no;
} s[100];

//附,大概 getchar(卡塔尔国;  会派上用项 

int i,n;

 

int cmp(const void *a,const void *b)
{
     struct node *aa=(node *)a;
     struct node *bb=(node *)b;
     if(aa->date1!=bb->date1)
         return(((aa->date1)>(bb->date1))?1:-1);
     else
         return((aa->no)-(bb->no));
}

三、对double类型数组排序(特别要留意)

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++)
     {
         s[i].no=i+1;
         scanf(“%lf”,&s[i].date1);
     }
     qsort(s,n,sizeof(s[0]),cmp);

double in[100];

     for(i=0;i<n;i++) printf(“%d   %lfn”,s[i].no,s[i].date1);

int cmp( const void *a , const void *b )

     return(0);
}

{

No.7.对字符串数组的排序(char s[][]型)

return *(double *)a > *(double *)b ? 1 : -1;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//再次来到值的难点,显明cmp重临的是三个整型,所以避免double重回小数而被错过,用一个剖断重回值。

char s[100][100];
int i,n;

}

int cmp(const void *a,const void *b)
{
     return(strcmp((char*)a,(char*)b));
}

qsort(in,100,sizeof(in[0]),cmp);

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++) scanf(“%s”,s[i]);

 //附:排序结果的出口,经常建议用 “ %g ” 格式

    
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf(“%sn”,s[i]);
    
     return(0);
}

/* 在那间多嘴一句,”%g”格式输出 即便书上是说系统会自动采用 ” %f ” 格式
 和 ” %e ” 格式
中长度非常的短的格式,并去掉无意义的0,但事实上系统黄金年代旦选择了” %e
“,系统会输出比 “ %e ”
格式更省壹位的格式输出。(此结论,来自VC6.0的实操)*/

No.8.对字符串数组排序(char *s[]型)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

 

char *s[100];
int i,n;

四、对布局体超级排序

int cmp(const void *a,const void *b)

struct In

{
     return(strcmp(*(char**)a,*(char**)b));
}

{

int main()
{
     scanf(“%d”,&n);
     for(i=0;i<n;i++)
     {
         s[i]=(char*)malloc(sizeof(char*));
         scanf(“%s”,s[i]);
     }

double data;

     qsort(s,n,sizeof(s[0]),cmp);

int other;

     for(i=0;i<n;i++) printf(“%sn”,s[i]);

}s[100]

     return(0);
}

 

//依据data的值从小到老马布局体排序,关于组织体内的排序关键数据data的体系能够多二种,参照他事他说加以考查下面的例证写

 

int cmp( const void *a ,const void *b)

{

return (*(In *)a).data > (*(In *)b).data ? 1 : -1;

//注意,那条语句在VC6.0景况下运转可能会出错,可是并不是语句错了,而是你要先
Build ,或然全体重新建构。一句话来讲语句是没错。

//或然你能够将那上头1条语句改成上边那3条语句

//struct In *aa = (In *)a;
//struct In *bb = (In *)b;
//return aa->data > bb->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);

 

小心!qsort 中的  cmp 得和煦写 。

 

 

再说说   sort (常用于  C++ )

sort 使用时得注脚:using namespace std;   或间接打 std::sort(卡塔尔(قطر‎ 
还得加上  #include <algorithm> 头文件

 

例:

#include<iostream>

#include<algorithm>

using namespace std;

 

int main()

{

       int a[20];

   for(int i=0;i<20;++i)

              cin>>a[i];

 

     sort(a,a+20卡塔尔国;             //范围,很鲜明这里是a+20
注意,那是必须的,假如是a+19

       for(i=0;i<20;i++卡塔尔(قطر‎        //最后一个值a[19]就不会到场排序。

              cout<<a[i]<<endl;

       return 0;

}

 

std::sort是三个改进版的qsort.
std::sort函数优于qsort的部分特点:对大数组选取9项取样,更完全的三路划分算法,更周详的对不相同数组大小接纳差别方法排序。

 

 

 

最终,大家来讲说sort、qsort的界别:

 

sort是qsort的升迁版,借使能用sort尽量用sort,使用也比较轻松,不像qsort还得自身去写
cmp 函数,只要评释 
使用的库函数就可以动用,参数唯有多少个(假使是日常用法)头指针和尾指针;

 

私下认可sort排序后是升序,假如想让他降序排列,能够运用本身编的cmp函数

#include<iostream>
#include<algorithm>
using namespace std;
int cmp(int a,int b)
{
  if(a<b)
  return 1; //升序排列,若是改为 a
>b,则为降序,要注意sort(State of Qatar中cmp(卡塔尔的返值只有1和0,不像qsort中设有-1!!!!
  else
  return 0;
}

int main(){
    int i;
 int a[20];
 for(int i=0;i<5;++i)
  cin>>a[i];

sort(a,a+5,cmp卡塔尔;          //范围,很掌握这里是a+5
注意,那是少不了的,假设是a+4最后二个值a[4]就不会加入排序。
for(i=0;i<5;i++)       

cout<<a[i]<<endl;
    system(“pause”);
 return 0;
}

 

对二维数组的排序:
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

bool cmp(int *p,int *q)
{
    if(p[0]==q[0])
    {
        if(p[1]==q[1])
        {
            return p[2]<q[2];
        }
        else return p[1]<q[1];
    }
    else return p[0]<q[0];
}
int main()
{
    srand(time(0));
    int i;
    int **a=new int*[1000];
    for(i=0;i<1000;++i)
    {
        a[i]=new int[3];
        a[i][0]=rand()%1000;
        a[i][1]=rand()%1000;
        a[i][2]=rand()%1000;
       
//printf(“%dt%dt%dn”,a[i][0],a[i][1],a[i][2]);
    }
    sort(a,a+1000,cmp);
    /*cout<<“After sort”<<endl;
    for(i=0;i<1000;++i)
    {
        printf(“%dt%dt%dn”,a[i][0],a[i][1],a[i][2]);
    }*/
    return 0;
}

 

之所以啊,有事没事,大家也得以看看 C++ .

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图