C语言中qsort函数使用及其模拟实现教程

目录

• 一、qsort函数简介
• 参数说明
• 二、qsort使用示例
• 1、使用qsort排序整型数据
• 1. 比较函数的基本要求
• 2. 为什么使用const void*参数
• 3. 具体实现解析
• 4. 内存视角分析
• 2、使用qsort排序结构体数据
• 1. 按年龄比较的函数
• 2. 按姓名比较的函数
• 三、qsort函数的模拟实现
• 1、比较函数int_cmp
• 2、交换函数_swap
• 3、冒泡排序函数bubble_sort
• 4、主函数main
• 关于void*指针的说明
• 总结

一、qsort函数简介

qsort是C标准库中的一个快速排序函数，位于stdlib.h头文件中。它的原型如下：

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

参数说明

• base: 指向要排序数组的第一个元素的指针

• nitems: 数组中元素的个数

• size: 数组中每个元素的大小（以字节为单位）

• compar: 用于比较两个元素的函数指针

二、qsort使用示例

1、使用qsort排序整型数据

#include <stdio.h>
#include <stdlib.h>  // 需要包含stdlib.h以使用qsort

// qsort函数的使用者需要实现一个比较函数
int int_cmp(const void *p1, const void *p2)
{
    return (*(int*)p1 - *(int*)p2);  // 升序排列
    // 若要降序排列，可以改为 return (*(int*)p2 - *(int*)p1);
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int i = 0;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    qsort(arr, size, sizeof(int), int_cmp);
    
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

1. 比较函数的基本要求

qsort的比较函数需要遵循以下规则：

• 接受两个const void*参数（指向要比较元素的指针）

• 返回一个int值表示比较结果：

  • 负数：第一个参数小于第二个参数

  • 零：两个参数相等

  • 正数：第一个参数大于第二个参数

2. 为什么使用const void*参数

1. 通用性：void*可以指向任何数据类型，使qsort能处理各种类型的数组

2. 安全性：const修饰确保函数不会修改原始数据

3. 标准化：这是C标准库规定的接口形式

3. 具体实现解析

int int_cmp(const void *p1, const void *p2)
{
    return (*(int*)p1 - *(int*)p2);  // 升序排列
}

关键步骤：

1. 类型转换：

   • (int*)p1：将void指针转换为int指针

   • *(int*)p1：解引用获取实际的整数值

2. 比较运算：a - b的结果：

   • 若a > b → 结果为正 → 表示a应该在b后面（升序）

   • 若a == b → 结果为0 → 表示两者相等

   • 若a < b → 结果为负 → 表示a应该在b前面（升序）

3. 升降序控制：

   • 升序：return a - b（参数1 - 参数2）

   • 降序：return b - a（参数2 - 参数1）

4. 内存视角分析

假设我们有数组[3,1]，比较过程：

1. qsorphpt传入的是&arr[0]和&arr[1]（void指针）

2. 比较函数内：

   • 转换为int指针后解引用得到3和1

   • 计算3 - 1 = 2（正数）

   • 表示3 > 1，需要交换位置

2、使用qsort排序结构体数据

#include <stdio.h>
#include <stdlib.h>
#include <string.h>  // 需要包含string.h以使用strcmp

struct Stu {        // 学生结构体
    char name[20];  // 名字
    int age;        // 年龄
};

// 按照年龄来比较
int cmp_stu_by_age(const void *e1, const void *e2)
{
    return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

// 按照名字来比较
int cmp_stu_by_name(const void *e1, const void *e2)
{
    // strcmp是库函数，专门用来比较两CwehMZxIvq个字符串的大小
    return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

// 按照年龄来排序
void test_age_sort()
{
    struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15}};
    int sz = sizeof(s) / sizeof(s[0]);
    
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
    
    // 打印排序结果
    for (int i = 0; i < sz; i++) {
        printf("%s %d\n", s[i].name, s[i].age);
    }
}

// 按照名字来排序
void test_name_sort()
{
    struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15}};
    int sz = sizeof(s) / sizeof(s[0]);
    
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
    
    // 打印排序结果
    for (int i = 0; i < sz; i++) {
        printf("%s %d\n", s[i].name, s[i].age);
    }
}

int main()
{
    printf("按年龄排序:\n");
    test_age_sort();
    
    printf("\n按姓名排序:\n");
    test_name_sort();
    
    return 0;
}

这段代码展示了如何使用C标准库中的qsort函数对结构体数组进行排序，重点在于两个比较函数cmp_stu_by_age和cmp_stu_by_name的实现。

1. 按年龄比较的函数

int cmp_stu_by_age(const void *e1, const void *e2)
{
    return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

工作原理：

1. 参数是两个void*指针，这是qsort函数要求的比较函数格式

2. 将void*指针转换为struct Stu*类型

3. 比较两个学生的年龄字段age

4. 返回两者的差值

返回值含义：

• 如果第一个学生的年龄小于第二个学生，返回负值

• 如果两者年龄相等，返回0

• 如果第一个学生的年龄大于第二个学生，返回正值

特点：

• 简单直接，适合数值类型的比较

• 对于整数比较很有效

2. 按姓名比较的函数

int cmp_stu_by_name(const void *e1, const void *e2)
{
    return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

工作原理：

1. 同样接收两个void*指针参数

2. 将指针转换为struct Stu*类型

3. 使用strcmp函数比较两个学生的name字符串（后面到字符串部分会讲解）

4. 直接返回strcmp的结果

返回值含义：

• 如果第一个名字在字典序中排在第二个名字之前，返回负值

• 如果两个名字相同，返回0

• 如果第一个名字在字典序中排在第二个名字之后，返回正值

特点：

• 使用标准库函数strcmp进行字符串比较

• 遵循字典序（lexicographical order）比较规则

• 比较是基于ASCII值的逐个字符比较

三、qsort函数的模拟实现

下面使用回调函数和冒泡排序的方式模拟实现qsort：

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

// 比较函数，用于整型比较
int int_cmp(const void *p1, const void *p2)
{
    return (*(int*)p1 - *(int*)p2);
}

// 交换函数，逐字节交换两个元素
void _swap(void *p1, void *p2, int size)
{
    for (int i = 0; i < size; i++) {
        char tmp = *((char*)p1 + i);
        *((char*)p1 + i) = *((char*)p2 + i);
        *((char*)p2 + i) = tmp;
    }
}

// 模拟qsort的冒泡排序实现
void bubble_sort(void *base, int count, int size, int(*cmp)(const void*, const void*))
{
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            // 计算两个要比较元素的地址
            void *elem1 = (char*)base + j * size;
            void *elem2 = (char*)base + (j + 1) * size;
            
            if (cmp(elem1, elem2) > 0) {  // 如果前一个元素大于后一个元素
                _swap(elem1, elem2, size); // 交换两个元素
            }
        }
    }
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    bubble_sort(arr, size, sizeof(int), int_cmp);
    
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

这段代码实现了一个通用的冒泡排序函数，模仿了C标准库中的qsort函数的行为。下面我将详细解释各个部分：

1、比较函数int_cmp

int int_cmp(const void *p1, const void *p2)
{
    return (*(int*)p1 - *(int*)p2);
}

• 这是一个用于比较整数的函数

• 参数是两个void指针，可以指向任何类型的数据

• 通过强制类型转换(int*)将指针转换为整型指针，然后解引用获取整数值

• 返回值为：

  • 负数：如果p1指向的值小于p2指向的值

  • 零：如果两者相等

  • 正数：如果p1指向的值大于p2指向的值

2、交换函数_swap

void _swap(void *p1, void *p2, int size)
{
    for (int i = 0; i < size; i++) {
        char tmp = *((char*)p1 + i);
        *((char*)p1 + i) = *((char*)p2 + i);
        *((char*)p2 + i) = tmp;
    }
}

• 这个函数用于交换两个内存块的内容

• 参数：

  • p1, p2: 要交换的两个内存块javascript的指针

  • size: 每个内存块的大小（字节数）

• 实现方式：

  • 将指针转换为char*（因为char是1字节）

  • 逐字节交换两个内存块的内容

• 这种实现方式可以处理任何数据类型

3、冒泡排序函数bubble_sort

void bubble_sort(void *base, int count, int size, int(*cmp)(const void*, const void*))
{
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            void *elem1 = (char*)base + j * size;
            void *elem2 = (char*)base + (j + 1) * size;
            
            if (cmp(elem1, elem2) > 0) {
                _swap(elem1, elem2, size);
            }
        }
    }
}

• 这是一个通用的冒泡排序实现

• 参数：

  • base: 数组的起始地址

  • count: 数组中元素的数量www.devze.com

  • size: 每个元素的大小（字节数）

  • cmp: 比较函数编程客栈的指针

• 实现要点：

  1. 外层循环控制排序轮数

  2. 内层循环比较相邻元素

  3. 通过(char*)base + j * size计算元素地址（因为char指针算术运算以字节为单位）

  4. 使用用户提供的比较函数来决定是否需要交换

  5. 需要交换时调用_swap函数

4、主函数main

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    bubble_sort(arr, size, sizeof(int), int_cmp);
    
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

• 创建一个整型数组并初始化

• 计算数组大小

• 调用bubble_sort进行排序，传入：

  • 数组地址

  • 元素数量

  • 每个元素的大小（sizeof(int)）

  • 比较函数int_cmp

• 打印排序后的数组

关于void*指针的说明

在模拟实现中，我们使用了void*指针，这是C语言中的通用指针类型，可以指向任何类型的数据。它的特点包括：

1. void*指针可以接收任何类型的指针

2. 不能直接对void*指针进行解引用操作

3. 不能对void*指针进行算术运算

4. 使用前需要先转换为具体类型的指针

在排序函数中，我们通过将void*转换为char*并进行指针算术运算来访问数组元素，这是因为char类型的大小为1字节，可以方便地进行字节级别的操作。

总结

到此这篇关于C语言中qsort函数使用及其模拟实现的文章就介绍到这了,更多相关qsort函数使用及模拟实现内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！