C语言qsort函数详解与实现（快速排序任何类型）
C语言qsort函数详解与实现（快速排序任何类型）
本文详细介绍了C语言中的qsort函数。从函数的定义开始，解释了其参数的意义，特别是compar函数指针的作用。接着通过多个实例展示了如何使用qsort函数对不同数据类型（整形、浮点型、字符数组、结构体）进行排序。最后，文章还展示了如何用冒泡排序实现qsort函数的功能，并通过多个检测函数验证了其实现的正确性。
一. 介绍 qsort 函数
我们以前学习过一些排序算法，如冒泡，选择，归并，快速排序等等，它们排序的速度有快有慢，但这些排序都只能排序一种类型的数据，如果想再排序另外一种类型得数据就需要再另写一个排序，所以有没有什么排序是万能的，既能排整形，又能排浮点型，还能排字符串类型等等的排序呢？
答案是有的，它就是 qsort 函数。
qsort 函数官方定义：
形式就是：
void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));
// base -> 需要排序的数组的起始地址
// num -> 数组内元素的个数（数组的大小）
// size -> 一个元素的大小（单位是字节）
// int (*compar)(const void*,const void*) -> compar(一个函数指针)，类型是 int (*)(const void*,const void*)
大家也都能了解，这个函数的重点就在于 compar 这一函数指针。
分析 compar 函数指针：
在排序时，比较整形，浮点型都可以使用大于，小于，等于号直接比较大小，比较字符串可以使用 strcmp 函数；但是若要比较结构体呢？结构体内含有多种数据类型，此时若要比较就得写出多个排序函数，但是在 qsort 函数内 ，有了 compar 函数指针这种问题就能轻易的被实现。
compar 函数指针：我们发现给它传递的是两个 const void* 类型的指针，返回的是 int 类型的数字，也看到官方的讲解（若传递 p1指针和 p2 指针）其返回的是-1（*p1<*p2），0（*p1==*p2），1（*p1>*p2）。
按照 compar 定义，数组是以升序的顺序进行排序的，但是若要以降序的顺序进行排序，则就将函数内部返回时的 p1 与 p2 进行颠倒。具体实现看以下实例。
二. qsort 函数使用方法
因为 qsort 函数是一个库函数，所以在使用时需要包含一个头文件 #include<stdlib.h>
在写好 qsort 函数内的变量时，需要再写一个 compar 指针函数所指向的函数。新函数内部的 p1 和 p2 一定要强制类型转换成要排序的数组的类型。
三. qsort 函数使用实例
1. qsort 函数排序整形
#include<stdio.h>
int smp_int(const void* p1, const void* p2)
{
// return (int)(*(int*)p1 - *(int*)p2); //->升序
return (int)(*(int*)p2 - *(int*)p1); //->降序
}
int main()
{
int arr[] = { 2,4,1,6,8,4,9,3,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), smp_int);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
我们发现：smp_int 函数内在返回时，都先将 p1 和 p2 两个指针强制类型转换成 int* 类型，再进行解引用操作，再相减。因为此函数最终返回的结果是 int 类型，所以最后再将得出的结果强制转化成 int 类型。
2. qsort 函数排序浮点型
#include<stdio.h>
int smp_double(const void* p1, const void* p2)
{
return (int)(*(double*)p1 - *(double*)p2); //升序
}
int main()
{
double arr[] = { 2.3,4.7,1.1,6.5,8.8,4.9,9.2,43.5,7.77 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), smp_double);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%.2lf ", arr[i]);
}
return 0;
}
此代码与 排序整形 有异曲同工之处。大家可试着分析。
3. qsort 函数排序字符数组
#include<stdio.h>
int smp_char(const void* p1, const void* p2)
{
return (int)(*(char*)p1 - *(char*)p2);
}
int main()
{
char arr[] = { 'b','a','y','d','f'};
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), smp_char);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%c ", arr[i]);
}
return 0;
}
字符在排序时：'a'< 'b' < 'c' < ... < 'y' < 'z'。
4. qsort 函数排序结构体
#include<stdio.h>
struct Book
{
char name[30]; // 书名
char author[20]; // 作者
double price; // 价钱
};
int smp_name(const void* p1, const void* p2)
{
return strcmp(((struct Book*)p1)->name, ((struct Book*)p2)->name);
}
void Print_name(struct Book* b1,int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%-30s\t%-20s\t%.1lf\n", b1[i].name, b1[i].author, b1[i].price);
}
}
int main()
{
struct Book b1[] = { {"《C语言》","张三",49.9},{"《数据结构》","李四",59.9},{"《英语》","王五",12.8},{"《Python程序基础》","阿牛",47.8} };
int sz = sizeof(b1) / sizeof(b1[0]);
qsort(b1, sz, sizeof(b1[0]), smp_name);
Print_name(b1,sz);
return 0;
}
排序结构体分析：此代码先定义一个结构体（描述一些类型），在写 smp_name 代码时，需要将两个指针先转换为结构体类型的指针，比较什么数据，就让其指向什么数据，因为其比较的是字符串类型的数据，所以字符串的比较用的是 strcmp 函数。
四. 冒泡排序实现 qsort 函数
库函数内的qsort 函数实现是用快速排序写成的，但是为了大家更好的方便理解 qsort 函数这一实现过程，此处用冒泡排序实现 qsort 函数。
void Swap(char* buf1, char* buf2,int size)
{
char tmp = 0;
int i = size;
while (i--)
{
tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void my_qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{
int i = 0;
for (i = 0; i < num-1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
Swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
}
}
}
相信大家肯定对这两行代码有疑惑：
if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
Swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
在分析之前，大家先看这张图片：
其代表了所有函数与函数之间的调用情况和联系（有助于大家理解）。
分析代码：
在实现 qsort 函数时，因为函数所接收来的数组是void类型的，不知道元素具体是什么类型，无法使用下标来访问数组内的元素，故此只能将base强制转换成char类型的，因为char类型每次移动的字节数是一个字节，使用char类型就能在保证不遗落字节的情况下，访问到数组空间内所有的字节，因为每两个元素之间相隔一个size 大小字节的宽度，所以 用（char*）base+j * size来取出第一个元素的地址，用(char*) base+(j+1)*size取出第二个元素的地址，然后将它们再放入到smp_int 函数中进行比较。之后再依次取出之后元素的地址，再次比较。
int smp_int(const void* p1, const void* p2)
{
return (int)(*(int*)p1 - *(int*)p2);
}
比较之后，若两个元素需要交换时，因为事先并不知道元素是什么类型，所以还得用到 char* 类型来一个字节一个字节的进行交换。
void Swap(char* buf1, char* buf2,int size)
{
char tmp = 0;
int i = size;
while (i--)
{
tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
检测函数实现情况：
1. 检测整形
#include<stdio.h>
int smp_int(const void* p1, const void* p2)
{
return (int)(*(int*)p1 - *(int*)p2);
}
int main()
{
int arr[] = { 2,4,1,6,8,4,9,3,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(arr[0]), smp_int);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
运行结果：
2. 检测浮点型
#include<stdio.h>
int smp_double(const void* p1, const void* p2)
{
return (int)(*(double*)p1 - *(double*)p2);
}
int main()
{
double arr[] = { 2.3,4.7,1.1,6.5,8.8,4.9,9.2,43.5,7.77 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(arr[0]), smp_double);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%.2lf ", arr[i]);
}
return 0;
}
代码运行结果：
3. 检测字符数组
#include<stdio.h>
int smp_char(const void* p1, const void* p2)
{
return (int)(*(char*)p1 - *(char*)p2);
}
int main()
{
char arr[] = { 'b','a','y','d','f' };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(arr[0]), smp_char);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%c ", arr[i]);
}
return 0;
}
代码运行结果：
4. 检测结构体
#include<stdio.h>
struct Book
{
char name[30]; // 书名
char author[20]; // 作者
double price; // 价钱
};
int smp_author(const void* p1, const void* p2)
{
return strcmp(((struct Book*)p1)->author, ((struct Book*)p2)->author);
}
void Print_author(struct Book* b1, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%-20s\t%-30s\t%.1lf\n", b1[i].author, b1[i].name, b1[i].price);
}
}
int main()
{
struct Book b1[] = { {"《C语言》","张三",49.9},{"《数据结构》","李四",59.9},{"《英语》","王五",12.8},{"《Python程序基础》","阿牛",47.8} };
int sz = sizeof(b1) / sizeof(b1[0]);
my_qsort(b1, sz, sizeof(b1[0]), smp_author);
Print_author(b1, sz);
return 0;
}
代码运行结果：