logo资料库

快速排序库函数qsort的调用细则.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.02M 资料格式：docx 举报 版权申诉
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
资料共5页，全文预览结束
    快速排序库函数 qsort 调用细则 关于快排，其原理及实现网上可以找到很多，我给出的那些动画视频链接里面也有形象 的演示，可以上网搜到很多，这里主要讲的是怎样调用系统提供的快排库函数：qsort，它 包含在头文件里,函数一共四个参数,在函数头部加上#include,就可以直接 调用，并且无需声明。一个典型的 qsort 的写法如下： qsort(s,n,sizeof(s[0]),cmp); 其中第一个参数 s 是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写成 &s[i]这样的表达式,这个问题下面有说明); 第二个参数 n 是参与排序的元素个数; 第三个参 数是单个元素的大小,必须 sizeof(s[0])这样的表达式,下面也有说明；第四个参数 cmp 其实是 个函数名字，它是为指导 qsort 如何进行排序而专门写的一个函数，我们称之为比较函数， 其目的是为了告诉 qsort 要以什么样的方式进行排序（降序？升序？或者按照某个关键字进 行排序等）（注：写成 cmp 只是一个名字,可以随便怎么写)，cmp 这个函数有形参，和返回 值（int 型），但是在调用时却不需要给它传递实参进去，直接调用其名字即可，这个函数是 专门为 qsort 开发的一种函数形式，这个函数的典型定义是: int cmp(const void *a,const void *b)；（红色字体是其固定模式，必须这样写，黑色的则是自 己随便起的名字）（其函数体详见后面），并且规定这个函数只能返回 int 型值。 关于快排的一些小问题 1.快排的复杂度，当元素个数比较少时（10^2 的数量级左右），快排的速度跟冒泡相比并没 有快很多，还有如果要排序的元素大部分都已经是排好顺序了时，快排效率会下降，但是其 最坏情况是 N^2（当元素全部是已经排好的顺序时），一般情况（也即平均效率）是 N*Log2 （N），最好情况是 N(当元素全部是逆序时)，快排的特点是元素越乱排序速度越快，所以可 以看出，虽然元素少时使用快排并没有很大优势，但是在快排的最坏情况跟冒泡、选择排序 （冒泡、选择排序其复杂度不受元素顺序影响，永远为 N^2）一样，所以快排永远是最快的。 2.快排是不稳定的，这里的稳定性是指对于相同元素的处理上，快排会打乱相同元素的先后 顺序（原因就在于快排排序原理，其排序过程是不断把元素分组打乱进行的），当然如果单 纯排序一列数字是没什么区别的，假设我们有这样一列数字 3，3，3，但是三个 3 是有区别 的,我们标记为 3a,3b,3c,快排后的结果不一定就是 3a,3b,3c 这样的排列,所以在某些特定场合 我们要用结构体来使其稳定(No.5 的例子就是说明这个问题的) 3.快排的比较函数 cmp 的两个参数必须都是 const void *的,这个要特别注意,写 a 和 b 只是个 人喜好,写成 cmp 也只是个人喜好. 4.快排 qsort 的第三个参数,sizeof,推荐是使用 sizeof(s[0])这样,特别是对结构体,往往自己定义 2*sizeof(int)这样的会出问题,用 sizeof(s[0)既方便又保险 5.如果要对数组进行部分排序,比如对一个 s[n]的数组，要对其从 s[i]开始的 m 个元素进行排 序,只需要在第一个和第二个参数上进行一些修改:qsort(&s[i],m,sizeof(s[i]),cmp); 注：以下所有程序都已经在 visual studio 2008 上编译通过 No.1 最常见的,对 int 数组排序 #include #include #include int s[10000],n,i; int cmp(const void *a, const void *b) { return(*(int *)a-*(int *)b);/*这里的（int *）a 定义了一个指向 int 型的指针，注意 int *两
    边的括号不能少，然后（int *）a 前面加上*就表示取其指向的值。这里返回的是*(int *)a-*(int *)b，两个数相减的顺序跟函数形参顺序一样这样就会将数组按升序排序，反之如果是 return(*(int *)b-*(int *)a)，就会将数组按降序排列*/ } void main() { scanf("%d",&n); for(i=0;i #include double s[1000]; int i,n; int cmp(const void * a, const void * b) { return((*(double*)a-*(double*)b>0)?1:-1);/*注意这里不能像上面对 int 型数组排序时那样 直接返回*(double*)a-*(double*)b，因为这个 cmp 函数的返回值已经规定了是 int 型，而 *(double*)a-*(double*)b 是 double 型，这里是对这个 double 型数组进行了升序排列，如果 return((*(double*)b-*(double*)a>0)?1:-1)或者 return((*(double*)a-*(double*)b>0)?-1:1)则对数 组进行降序排列*/ } void main() { scanf("%d",&n); for(i=0;i #include #include char s[10000],i,n; int cmp(const void *a,const void *b) {
    return(*(char *)a-*(char *)b);//这里直接把字符的 ASCII 码相减来比较字符的先后顺序 } int main() { scanf("%s",s); n=strlen(s); qsort(s,n,sizeof(s[0]),cmp); printf("%s",s); } No.4 对结构体排序 #include #include struct node { double date; int flag; } s[100]; int i,n; int cmp(const void *a,const void *b) { return(((struct node *)a)->date > ((struct node *)b)->date?1:-1);/*注意，这里的 struct node *跟前面的 int*,double*原理一样，都是一种指针类型，这里是自己定义的一个指向结构体的 指针类型，故写法为 struct 结构体名称 *，这里 date 是 double 型数据，故不可能有相等情 况出现，只需返回 1 和-1 即可*/ } int main() { scanf("%d",&n); for(i=0;i #include struct node { double date;
    int flag; } s[100]; int i,n; int cmp(const void *a,const void *b) { if(((struct node *)a)->date !=( (struct node *)b)->date) return(((struct node *)a)->date > ((struct node *)b)->date?1:-1); return(((struct node *)a)->flag - ((struct node *)b)->flag); else } int main() { scanf("%d",&n); for(i=0;i #include #include char s[100][100]; int i,n; int cmp(const void *a,const void *b) { return(strcmp((char*)a,(char*)b));/*这里调用了 strcmp 比较函数，这个函数根据字典序对 字符串进行比较，按字符串的先后顺序依次返回 1 或 0 或-1*/ } void main() { scanf("%d",&n); for(i=0;i
    #include #include char *s[100];//定义了一个指针数组，亦可称为指针的指针 int i,n; int cmp(const void *a,const void *b) { return(strcmp(*(char**)a,*(char**)b));//注意这里使用 char**表示指针的指针 } int main() { scanf("%d",&n); for(i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料