[数据结构与算法]C++学习笔记之qsort函数

?

一、qsort()函数

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

需要四个参数：待排序数组首地址；数组中待排序元素数量；各元素的占用空间的大小；指向函数的指针，用于确定排序的顺序。

时间复杂度为O(n*logn)。在qsort加入比较函数可以让qsort更有通用性 可以比较数组字符串和结构体；

如int cmp(const void *a, const void *b)中有两个元素作为参数（参数的格式不能变的。）返回一个int值，如果比较函数返回大于0，qsort就认为a > b，返回小于0,qsort就认为a < b。

cmp函数按照不同类型进行不同定义

:int

int num[100];
int cmp(const void *a, const void *b)
{
return  *(int *)a - *(int *)b;      //升序
return  *(int *)b - *(int *)a;      //降序
}

char

char num[100];
int cmp(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}

qsort(num, 100, sizeof(char), cmp);

其它类型基本类型同理；

但结构体类型参照下文代码！?

实现：有N个学生的数据，将学生数据按成绩高低排序，如果成绩相同则按姓名字符的字母排序，如果姓名的字母序也相同，则按照学生的年龄排序，并输出N个学生排序后的信息。

struct Stud {char name[20];? int age；?int score;};

1.定义结构体类型 2.定义输出结构体函数

3.定义一个cmp函数用来实现数组的排序：实现这个功能需要cmp函数进行三级排序，首先是对成绩的高低经行升序（降序）排列，成绩相同时按照年龄进行升序（降序排列），如果年龄也相同则按照名字的来进行排序

代码实现如下：

有N个学生的数据，将学生数据按成绩高低排序，如果成绩相同则按姓名字符的字母排序，
//如果姓名的字母序也相同，则按照学生的年龄排序，
//并输出N个学生排序后的信息。
#include<iostream>
using namespace std;
#define N 5
struct Stud 
{
	char name[20];
	int age;
	int score;
}stud[N];
int cmp(const void* a, const void* b);
void show(Stud[]);
int main()
{
	for (int i = 0; i < N; i++)
	{
		cin >> stud[i].name;
		cin >> stud[i].age;
		cin >> stud[i].score;
	}
	cout << "================================================"<<endl;
	qsort(stud, N, sizeof(Stud), cmp);
	show(stud); 
}
int cmp(const void* a, const void* b)
{
	struct Stud* c = (Stud*)a;
	struct Stud* d = (Stud*)b;
	if (c->score != d->score)
	{
		return  (*c).score - (*d).score;			//降序
	}
	else if (c->age != d->age)
	{
		return (*c).age - (*d).age;					//return *(int*)b - *(int*)a;
	}
	else
		return *(char*)b - *(char*)a;
}
void show(Stud[])
{
	for (int i = 0; i < N; i++)
	{
		cout << stud[i].name<<" ";
		cout << stud[i].age<<" ";
		cout << stud[i].score<<" ";
		cout << endl;
	}
	
}