博客

C语言快速排序–qsort函数

一.什么是qsort函数

qsort函数是C语言编译器函数库自带的快速排序函数。

其包含在

#include<stdlib.h>

头文件里面，所以在使用的时候需要加上该头文件。

二.qsort函数的时间复杂度

因为其本身还是快速排序，所以时间复杂度仍然是O（nlogn）

（在洛谷做题的时候，感觉它还是比传统的快排要更快，传统的快排最后三个会TLE，但是使用qsort函数就不会）

三.具体讲解

1.描述

sqort函数对数组进行排序

2.声明

下面是 qsort() 函数的声明。

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

3.参数

base – 指向要排序的数组的第一个元素的指针。

nitems – 由 base 指向的数组中元素的个数。

size – 数组中每个元素的大小，以字节为单位。

compare – 用来比较两个元素的函数。

4.compare

自己定义一个compare函数，用来比较a和b的大小

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

（int *）a表示将a地址强制类型转换成整形地址类型
*(int*)a 就是得到目标地址的值

//对int型数据进行升序排序 
int compare1(const void *a,const void *b)
{
	return *(int*)a-*(int*)b;
}

//对int型数据进行降序排序 
//依次类推，所有的都可以这样进行降序排序
int compare2(const void *a,const void *b)
{
	return *(int*)b-*(int*)a;
}

//对double型数据进行升序排序 
int compare3(const void *a,const void *b)
{
	return *(double*)a-*(double*)b;
}

//对char型数据进行升序排序 
int compare4(const void *a,const void *b)
{
	return *(char*)a-*(char*)b;
}

//字符串长度排序 
int cmppare5(const void *a, const void *b)
{
    return strlen((char *)a) - strlen((char*)b);
}
//结构体排序
int compare6(const void *a,const void *b)
{
	return ((*(node*)a).x-(*(node*)b).x)==0?
	(*(node*)a).y-(*(node*)b).y:
	(*(node*)a).x-(*(node*)b).x;
}

升序排序：

*(int*)a-*(int*)b;


降序排序（a与b位置互换）：

*(int*)b-*(int*)a;


五.五种常用的qsort函数代码

1.int型

2.double型

3.char型

4.字符串型

5.结构体型

//1.对整数排序
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
int n,a[MAXN];

//升序排序
int compare1(const void *a,const void *b)
{
	return *(int*)a-*(int*)b;
}

//降序排序
int compare2(const void *a,const void *b)
{
	return *(int*)b-*(int*)a;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	qsort(a,n,sizeof(int),compare1);
	//qsort(a,n,sizeof(int),compare2);
	for(int i=0;i<n;i++)
		printf("%d ",a[i]);
	return 0;
}

//2.对double型排序
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
int n;
double a[MAXN];

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

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

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lf",&a[i]);
	qsort(a,n,sizeof(double),compare1);
	for(int i=0;i<n;i++)
		printf("%lf ",a[i]);
	return 0;
}

//3.对char型排序
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
int n;
char a[MAXN];

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

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

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf(" %c",&a[i]);
	qsort(a,n,sizeof(char),compare1);
	for(int i=0;i<n;i++)
		printf("%c ",a[i]);
	return 0;
}

//4.1对字符串排序
//按照长度大小排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 100010
int	 n;
char a[MAXN][MAXN];

int compare1(const void *a, const void *b)
{
	return strlen((char *)a) - strlen((char *)b);
} 

int compare2(const void *a, const void *b)
{
	return strlen((char *)b) - strlen((char *)a);
}

int main()
{
	scanf("%d",&n);
	getchar();		//吃掉换行符;
	for(int i=0;i<n;i++)
		gets(a[i]);
	qsort(a,n,sizeof(char)*MAXN,compare1);
	for(int i=0;i<n;i++)
	printf("%s\n",a[i]);
	return 0;
}

//4.2对字符串排序
//按照首字母大小排序
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
int	 n;
char a[MAXN][MAXN];

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

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

int main()
{
	scanf("%d",&n);
	getchar();		//吃掉换行符;
	for(int i=0;i<n;i++)
		gets(a[i]);
	qsort(a,n,sizeof(char)*MAXN,compare1);
	for(int i=0;i<n;i++)
	printf("%s\n",a[i]);
	return 0;
}

//5.对结构体排序
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
int	 n;
struct node{
	int x;
	char y;
}name[MAXN];

//对结构体中的x进行排序
int compare1(const void *a,const void *b)
{
	return (*(node*)a).x-(*(node*)b).x;
}

//对结构体中的y进行排序
int compare2(const void *a,const void *b)
{
	return (*(node*)a).y-(*(node*)b).y;
}

//利用三元运算符,将排序顺序改为：
//先按照结构体中的x进行排序，假如x相等的情况下，就按照y
//的值进行排序;
int compare3(const void *a,const void *b)
{
	return ((*(node*)a).x-(*(node*)b).x)==0?
	(*(node*)a).y-(*(node*)b).y:
	(*(node*)a).x-(*(node*)b).x;
}
int main()
{
	scanf("%d",&n);
	getchar();		//吃掉换行符;
	for(int i=0;i<n;i++)
		scanf("%d %c",&name[i].x,&name[i].y);
	qsort(name,n,sizeof(node),compare1);
	//qsort(name,n,sizeof(node),compare2);
	//qsort(name,n,sizeof(node),compare3);
	for(int i=0;i<n;i++)
	printf("%d %c\n",name[i].x,name[i].y);
	return 0;
}