C语言中qsort函数的详解，以及模拟

引言 

        C语言中qsort函数的详解和模拟实现qsort函数，这里为了使用冒泡排序来模拟qsort函数

一、详解qsort函数 

        在 C 语言中，qsort 函数是一个标准库函数，用于对数组进行快速排序（Quick Sort）。它位于 <stdlib.h> 头文件中，具有较高的通用性，可以对不同类型的数组进行排序。

函数原型： 

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

参数说明

• base：指向要排序的数组的第一个元素的指针。由于它是 void * 类型的指针，所以可以接受任意类型的数组。
• nmemb：数组中元素的个数，类型为 size_t，通常使用 sizeof 运算符来计算。
• size：每个元素的大小（以字节为单位），类型为 size_t，同样可以使用 sizeof 运算符来获取。
• compar：一个指向比较函数的指针，该比较函数用于确定元素的顺序。比较函数需要接受两个 const void * 类型的参数，并返回一个整数值，用于表示两个元素的大小关系。

比较函数： 

int compar(const void *a, const void *b);

• 参数：a 和 b 是指向要比较的两个元素的指针，类型为 const void *，在函数内部需要将其转换为实际的类型。
• 返回值：
  • 如果 *a 小于 *b，则返回一个负整数。
  • 如果 *a 等于 *b，则返回 0。
  • 如果 *a 大于 *b，则返回一个正整数。

二、qsort函数的使用 

        注意：qsort 函数是 C 语言中一个非常实用的排序工具，通过自定义比较函数，可以对不同类型的数组进行排序。需要注意的是，比较函数的实现要正确，以确保排序结果的正确性。

对整数数组进行排序

#include <stdio.h>
#include <stdlib.h>// 整数比较函数
int int_compare(const void *a, const void *b) {const int *pa = (const int *)a;const int *pb = (const int *)b;return (*pa - *pb);
}int main() {int arr[] = {5, 2, 8, 1, 9};int n = sizeof(arr) / sizeof(arr[0]);// 调用 qsort 函数进行排序qsort(arr, n, sizeof(int), int_compare);// 输出排序后的数组for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

 对结构体数据进行排序

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
struct Stu //学生
{char name[20];//名字int age; //年龄
};int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//先将数据转换成结构体对应的类型，然后比较
}int cmp_stu_by_age(const void* e1, const void* e2)
{return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);//先将数据转换成结构体对应的类型，然后比较
}
int main()
{struct Stu s[3] = { {"zhangsan", 20},{"lisi", 18}, {"wangwu", 23}};int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_name); //对结构体里面的名字按照字典序来比较for (int i = 0; i <= 2; i++){printf("%s ", s[i].name);}printf("\n");qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);//对结构体里面的年龄按照从小到大来排序for (int i = 0; i <= 2; i++){printf("%d ", s[i].age);}return 0;
}

 运行结果：

三、模拟qsort函数 

        这里是在冒泡排序的基础上，改编成qsort函数，可以先看学习一下冒泡排序是什么：

C语言实现冒泡排序，超详解-CSDN博客文章浏览阅读249次，点赞4次，收藏6次。用c语言实现使用冒泡排序https://blog.csdn.net/2401_88433210/article/details/146212798?spm=1011.2415.3001.10575&sharefrom=mp_manage_link这里只讲一下改编的核心思想：

       1.讲冒泡排序传入的参数设置成和qsort的参数一样

参数说明

• base：指向要排序的数组的第一个元素的指针。由于它是 void * 类型的指针，所以可以接受任意类型的数组。
• nmemb：数组中元素的个数，类型为 size_t，通常使用 sizeof 运算符来计算。
• size：每个元素的大小（以字节为单位），类型为 size_t，同样可以使用 sizeof 运算符来获取。
• compar：一个指向比较函数的指针，该比较函数用于确定元素的顺序。比较函数需要接受两个 const void * 类型的参数，并返回一个整数值，用于表示两个元素的大小关系。

        2.冒泡排序第二层循环里面的比较函数，使用参数部分传入的参数

        3.交换函数需要重新设计，因为是可以比较任何类型，所以也要交换任何类型的数据

 怎么实现交换任何类型的数据：

        这个问题的解决也非常的简单，众所周知，任何类型在内容中存储的一个单位是字节，只是字节的个数不一样，char类型是一个字节，int类型是4个字节，等等。

        所以可以直接交换数据在内存中的字节，如，int类型，可以交换内存中对应的4个字节。

         纯文字描述可能很难明白，这里得需要你的想像，想像有一排格子，其中四个格子对应一个int类型，借用第三者，依次交换每个格子里面的内容，将交换后的内容再解引用，就实现了数据的交换。

 核心参考代码：

#include <stdio.h>
int int_cmp(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}
void _swap(void* p1, void* p2, int size)
{int i = 0;for (i = 0; i < size; i++){char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}
void bubble(void* base, int count, int size, int(*cmp)(void*, void*))
{int i = 0;int j = 0;for (i = 0; i < count - 1; i++){for (j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){_swap((char*)base + j * size, (char*)base + (j + 1) * size,size);}}}
}

qsort参考代码：

#include <stdio.h>
int int_cmp(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}
void _swap(void* p1, void* p2, int size)
{int i = 0;for (i = 0; i < size; i++){char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}
void bubble(void* base, int count, int size, int(*cmp)(void*, void*))
{int i = 0;int j = 0;for (i = 0; i < count - 1; i++){for (j = 0; j < count - i - 1; j++){if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0){_swap((char*)base + j * size, (char*)base + (j + 1) * size,size);}}}
}
int main()
{int arr[] = { 1, 6, 0, 8, 9, 2, 4, 3, 7, 5 };int i = 0;bubble(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), int_cmp);for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}printf("\n");return 0;
}