C qsort排序函数

一、函数原型
qsort包含在<stdlib.h>头文件中,根据你给出的比较函数进行快速排序,通过指针移动实现排序,排序之后的结果仍然放在原数组中,使用qsort函数必须自己写一个比较函数。

函数原型:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void , const void))

参数:

base – 指向要排序的数组的第一个元素的指针。
nitems – 由 base 指向的数组中元素的个数。
size – 数组中每个元素的大小,以字节为单位。
compar – 用来比较两个元素的函数。
返回值: 无返回值。

二、函数解析
常见的qsort写法:void qsort(s, n, sizeof(s[0]), cmp);

第一个参数是参与排序的数组名(也就是开始排序的地址,所以&s[i],也是可以的)。
第二个参数是参与排序的元素的个数。
第三个参数是单个元素的大小(sizeof(s[0])这样就是获取到s[0]的元素大小)。
第四个参数是一个函数,定义qsort排序排序规则的函数。
比较函数
cmp比较函数(qsort它的比较函数名取什么都可以,cmp只是我看大家都这么写,习惯了!)

比较函数cmp的定义: int cmp(const void *a, const void *b);

返回值必须是int,两个参数的类型也必须是const void *。(变量名随意)
如果a与b的位置需要互换,则需要返回负值;若不需要互换,则返回非负值即可。(也就是负值是互换,非负值也维持原状)
若是对int排序,升序,如果a比b大返回一个正值,小则返回负值,相等返回0。(*(int*)a – *(int*)b返回值)
函数体内要对a,b进行强制类型转化后才能得到正确的值。((int*))

三、手写快排
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l – 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j — ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

四、使用qsort
1、对int数组排序
#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a, const void *b){
return *(int *)a – *(int *)b;//升序
// return *(int *)b – *(int *)a;//降序
}

int main()
{
int n,s[10000];
scanf(“%d”, &n);
for(int i=0;i<n;i++)
scanf(“%d”,&s[i]);
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%d “,s[i]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、对double数组排序
在对浮点或者double型的对其进行判断返回相应的数(可以使用三目运算符或者if语句),因为要是使用像整型那样相减的话,如果是两个很接近的数则可能返回一个很小的小数(大于-1,小于1),而cmp的返回值是int型,因此会将这个小数返回0,系统认为是相等,失去了本来存在的大小关系。

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

int cmp(const void *a, const void *b){
return ((*(double *)a – *(double *)b)>0?1:-1);//升序
// return ((*(double *)a – *(double *)b)<0?1:-1);//降序
}

int main()
{
int n;
double s[10000];
scanf(“%d”, &n);
for(int i=0;i<n;i++)
scanf(“%lf”,&s[i]);
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%lf “,s[i]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、对char数组排序
与int类型相似

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

int cmp(const void *a, const void *b){
return *(char *)a – *(char *)b;//升序
// return *(char *)b – *(char *)a;//降序
}

int main()
{
int n;
char s[10000];
scanf(“%d”, &n);
getchar();
for(int i=0;i<n;i++)
scanf(“%c”,&s[i]);
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%c “,s[i]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、对字符串排序
(1)char s[][]
strcmp() :字符串比较库函数,可以看看这篇博客博客

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

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

int main()
{
int n;
char s[1000][1000];
scanf(“%d”, &n);
for(int i=0;i<n;i++)
scanf(“%s”,s[i]);
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%d:%s\n”,i,s[i]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(2)char *s[]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

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

int main()
{
int n;
char *s[1000];
scanf(“%d”, &n);
for(int i=0;i<n;i++){
s[i] = (char *)malloc(sizeof(char *));//分配空间
scanf(“%s”,s[i]);
}
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%d:%s\n”,i,s[i]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
5、对结构体排序
(1)一级排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
int id;
}s[100];

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

int main()
{
int n;
scanf(“%d”, &n);
for(int i=0;i<n;i++)
scanf(“%d”,&s[i].id);
qsort(s, n, sizeof(s[0]), cmp);
for(int i=0;i<n;i++)
printf(“%d\n”,s[i].id);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(2)二级排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
int id;
char data;
}s[100];

int cmp(const void *a, const void *b){
struct node *aa = (node *)a;
struct node *bb = (node *)b;
if(aa->id == bb->id)//若id相同,按照data排序
return aa->data – bb->data;
else//否则按照id排序
return aa->id – bb->id;//升序
}

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

/*
5
1 c
1 b
1 a
2 a
3 a
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

五、例题
题目链接

复杂排序规则题

#include<stdio.h>
#include<stdlib.h>
struct Data{
long int id;
int d;
int c;
int tote;
};
struct Data s[4][100000],r;
int cmp(const void *a,const void *b){
struct Data e1=*(struct Data *)a;
struct Data e2=*(struct Data *)b;
if((e1.d+e1.c)!=(e2.d+e2.c)){
return (e2.d+e2.c)>(e1.d+e1.c);
}
else if(e1.d!=e2.d){
return e2.d>e1.d;
}
else{
return e1.id>e2.id;
}
}
int main()
{
int a,b,N,L,H,g[4]={0};
scanf(“%d %d %d”,&N,&L,&H);
for(a=0;a<N;a++){
scanf(“%ld %d %d”,&r.id,&r.d,&r.c);
r.tote=r.d+r.c;
if(r.d>=L&&r.c>=L){
if(r.d>=H&&r.c>=H){
b=0;
s[b][g[0]++]=r;
}
else if(r.d>=H){
b=1;
s[b][g[1]++]=r;
}
else if(r.d>=r.c){
b=2;
s[b][g[2]++]=r;
}
else{
b=3;
s[b][g[3]++]=r;
}
}
}
qsort(s[0],g[0],sizeof(s[0][0]),cmp);
qsort(s[1],g[1],sizeof(s[1][0]),cmp);
qsort(s[2],g[2],sizeof(s[2][0]),cmp);
qsort(s[3],g[3],sizeof(s[3][0]),cmp);
printf(“%d\n”,g[0]+g[1]+g[2]+g[3]);
for(a=0;a<4;a++)
for(b=0;b<g[a];b++)
printf(“%ld %d %d\n”,s[a][b].id,s[a][b].d,s[a][b].c);
return 0;
}