嵌入式(C语言篇)Day12

嵌入式Day12

一、qsort函数基础概述

（一）函数功能

• 作用：对任意类型数组进行排序，支持自定义比较规则，底层基于快速排序算法（不稳定排序）。
• 头文件：需包含 <stdlib.h>。

（二）函数原型

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

（三）参数解析

二、自定义比较函数compare

（一）函数要求

1. 返回值类型：int。
2. 参数类型：两个const void*指针，分别指向待比较的两个元素。
3. 逻辑规则：
   • 返回负数：表示第一个元素应排在第二个元素前面（即a < b）。
   • 返回正数：表示第一个元素应排在第二个元素后面（即a > b）。
   • 返回0：表示两个元素相等，排序中相对位置不保证（快排不稳定）。

（二）核心操作步骤

1. 指针类型转换：将void*指针强制转换为目标元素类型的指针（如int*、char*、结构体指针）。
2. 元素值比较：根据业务逻辑比较两个元素的值，返回相应符号的整数。

三、qsort函数使用场景与示例

（一）排序int数组

示例：降序排序

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

int compare_desc(const void *a, const void *b) {
    int num1 = *(int*)a;
    int num2 = *(int*)b;
    return num2 - num1; // 降序（num2 > num1时返回正数，num1排在后面）
}

int main() {
    int arr[] = {5, 2, 8, 1, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, len, sizeof(int), compare_desc); // 调用qsort
    // 输出结果：8 5 3 2 1
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

（二）排序字符串数组（字典序）

示例：升序字典序排序

#include <string.h>

int compare_str(const void *a, const void *b) {
    // a和b是指向char*的指针，需先解引用得到字符串指针
    char *str1 = *(char**)a;
    char *str2 = *(char**)b;
    return strcmp(str1, str2); // 升序字典序（strcmp返回负数/0/正数）
}

int main() {
    char *strs[] = {"apple", "banana", "cat", "dog"};
    int len = sizeof(strs) / sizeof(strs[0]);
    qsort(strs, len, sizeof(char*), compare_str);
    // 输出结果：apple banana cat dog
    for (int i = 0; i < len; i++) {
        printf("%s ", strs[i]);
    }
    return 0;
}

（三）排序结构体数组

结构体定义

typedef struct {
    int stu_id;       // 学号
    int total_score;  // 总分
    int age;          // 年龄
    char name[20];    // 姓名
} Student;

示例1：按总分升序排序

int compare_score(const void *a, const void *b) {
    Student *s1 = (Student*)a;
    Student *s2 = (Student*)b;
    return s1->total_score - s2->total_score; // 升序（总分小的在前）
}

示例2：按学号降序排序

int compare_id(const void *a, const void *b) {
    Student *s1 = (Student*)a;
    Student *s2 = (Student*)b;
    return s2->stu_id - s1->stu_id; // 降序（学号大的在前）
}

示例3：复合条件排序（总分降序→年龄升序→姓名字典序升序）

int compare_combined(const void *a, const void *b) {
    Student *s1 = (Student*)a;
    Student *s2 = (Student*)b;
    
    // 1. 总分降序
    if (s1->total_score != s2->total_score) {
        return s2->total_score - s1->total_score;
    }
    // 2. 年龄升序
    if (s1->age != s2->age) {
        return s1->age - s2->age;
    }
    // 3. 姓名升序字典序
    return strcmp(s1->name, s2->name);
}

四、注意事项与常见错误

（一）指针类型转换错误

• 错误示例：排序字符串数组时直接强转void*为char*（应为char**）。

  // 错误：a实际是char**类型，需先解引用
  char *str1 = (char*)a; // 错误，a是void*，指向char*元素（即二级指针）
  // 正确：先转为char**，再解引用得到char*
  char *str1 = *(char**)a; 
  

（二）比较函数返回逻辑错误

• 常见问题：返回值符号与排序顺序不匹配（如希望降序却返回a - b）。
• 解决方案：明确比较逻辑，可通过数学表达式目标顺序下的差值（如降序用b - a）。

（三）数组元素大小错误

• 错误示例：传递size参数时使用sizeof(数组名)而非sizeof(元素类型)。

  qsort(arr, len, sizeof(arr), compare); // 错误，sizeof(arr)是整个数组大小
  qsort(arr, len, sizeof(int), compare); // 正确，单个元素大小为sizeof(int)
  

（四）处理相等元素的稳定性

• qsort特性：快速排序不稳定，相同元素排序后相对位置可能改变。
• 适用场景：若需稳定排序，需自定义算法（如归并排序）或确保相等元素无需保留顺序。

五、扩展：qsort与冒泡排序对比

六、总结：qsort函数使用流程

1. 定义比较函数：根据需求编写compare函数，确保指针转换和返回逻辑正确。
2. 调用qsort：传入数组首地址、元素个数、单个元素大小及比较函数。
3. 验证结果：通过遍历数组或打印检查排序是否符合预期。

核心口诀：

• 指针转换要正确，类型匹配是关键。
• 比较函数返回值，符号决定前后序。
• 元素大小需精准，避免越界和错误。