C语言库函数——快排函数qsort()

目录

一、函数原型

二、函数介绍

三、函数使用

常见写法

比较函数

四、函数实例

1、int型数组

2、double型数组

3、char型数组

4、字符串

5、结构体

一级结构

二级结构

一、函数原型

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

二、函数介绍

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

注意：qsort()函数无返回值。

三、函数使用

常见写法：
（s、n、cmp均为样例名称，无特定含义，根据自己的定义改动即可）

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

函数参数个数：4

• s:参与排序的数组名
• n:参与排序的元素个数
• sizeof(s[0])：计算单个数组空间的大小（括号里面的s[0]只是随便挑选的，用于计算，此处也可以是s[1]或者其他，但是不可越界，根据自己习惯定义即可）
• cmp:比较函数（此部分需要自己完成）

比较函数：

函数模板：
注意：

• 比较函数为自定义函数
• 其两个参数为void*类型指针a和b，返回参数为整形int
• 参数类型为void*原因：不清楚需比较元素的类型是什么，所以通过void*类型指针的特点（可以接收任意类型的地址）来接收。
• const修饰其两个比较参数以防止其在使用时失误改动数据

int cmp(const void *a ,const void *b)  
{  
    return *(int *)a - *(int *)b ;  //从小到大排序，把a，b位置反过来就是从大到小   
}  

//或者

int cmp(const void *a ,const void *b)  
{  
    return *a - *b ;  //从小到大排序，把a，b位置反过来就是从大到小   
}  

四、函数实例

1、int型数组

#include <iostream>
using namespace std;

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

int main()
{
    int n, s[10000];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
       cin>>s[i];
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i]<<" ";
    }
    return 0;
}

2、double型数组

#include <iostream>
using namespace std;
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];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i] << " ";
    }
    return 0;
}

Tips:如果像整型那样相减的话，如果是两个很接近的数则可能返回一个很小的小数（大于-1，小于1），而cmp的返回值是int型，因此会将这个小数返回0，系统认为是相等，失去了本来存在的大小关系。

3、char型数组

#include <iostream>
using namespace std;
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];
    cin>>n;
    getchar();  //防止将换行操作误读取
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i] << " ";
    }
    return 0;
}

4、字符串

#include <iostream>
using namespace std;
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];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i] << endl;
    }
    return 0;
}

5、结构体

• 一级结构

#include <iostream>
using namespace std;
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;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i].id;
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i].id << endl;
    }
    return 0;
}

• 二级结构

#include <iostream>
using namespace std;
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;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i].id >> s[i].data;
    }
    qsort(s, n, sizeof(s[0]), cmp);
    for (int i = 0; i < n; i++)
    {
        cout << s[i].id << s[i].data << endl;
    }
    return 0;
}