C語言中qsort函數(shù)使用及其模擬實(shí)現(xiàn)教程
一、qsort函數(shù)簡介
qsort是C標(biāo)準(zhǔn)庫中的一個(gè)快速排序函數(shù)，位于stdlib.h頭文件中。它的原型如下：
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
參數(shù)說明
base: 指向要排序數(shù)組的第一個(gè)元素的指針
nitems: 數(shù)組中元素的個(gè)數(shù)
size: 數(shù)組中每個(gè)元素的大小（以字節(jié)為單位）
compar: 用于比較兩個(gè)元素的函數(shù)指針
二、qsort使用示例
1、使用qsort排序整型數(shù)據(jù)
#include <stdio.h>
#include <stdlib.h> // 需要包含stdlib.h以使用qsort
// qsort函數(shù)的使用者需要實(shí)現(xiàn)一個(gè)比較函數(shù)
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. 比較函數(shù)的基本要求
qsort的比較函數(shù)需要遵循以下規(guī)則：
接受兩個(gè)const void*參數(shù)（指向要比較元素的指針）
返回一個(gè)int值表示比較結(jié)果：
負(fù)數(shù)：第一個(gè)參數(shù)小于第二個(gè)參數(shù)
零：兩個(gè)參數(shù)相等
正數(shù)：第一個(gè)參數(shù)大于第二個(gè)參數(shù)
2. 為什么使用const void*參數(shù)
通用性：
void*可以指向任何數(shù)據(jù)類型，使qsort能處理各種類型的數(shù)組安全性：
const修飾確保函數(shù)不會(huì)修改原始數(shù)據(jù)標(biāo)準(zhǔn)化：這是C標(biāo)準(zhǔn)庫規(guī)定的接口形式
3. 具體實(shí)現(xiàn)解析
int int_cmp(const void *p1, const void *p2)
{
return (*(int*)p1 - *(int*)p2); // 升序排列
}關(guān)鍵步驟：
類型轉(zhuǎn)換：
(int*)p1：將void指針轉(zhuǎn)換為int指針
*(int*)p1：解引用獲取實(shí)際的整數(shù)值
比較運(yùn)算：a - b的結(jié)果：
若a > b → 結(jié)果為正 → 表示a應(yīng)該在b后面（升序）
若a == b → 結(jié)果為0 → 表示兩者相等
若a < b → 結(jié)果為負(fù) → 表示a應(yīng)該在b前面（升序）
升降序控制：
升序：return a - b（參數(shù)1 - 參數(shù)2）
降序：return b - a（參數(shù)2 - 參數(shù)1）
4. 內(nèi)存視角分析
假設(shè)我們有數(shù)組[3,1]，比較過程：
qsort傳入的是
&arr[0]和&arr[1]（void指針）比較函數(shù)內(nèi)：
轉(zhuǎn)換為int指針后解引用得到3和1
計(jì)算3 - 1 = 2（正數(shù)）
表示3 > 1，需要交換位置
2、使用qsort排序結(jié)構(gòu)體數(shù)據(jù)
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // 需要包含string.h以使用strcmp
struct Stu { // 學(xué)生結(jié)構(gòu)體
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是庫函數(shù)，專門用來比較兩個(gè)字符串的大小
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);
// 打印排序結(jié)果
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);
// 打印排序結(jié)果
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標(biāo)準(zhǔn)庫中的qsort函數(shù)對(duì)結(jié)構(gòu)體數(shù)組進(jìn)行排序，重點(diǎn)在于兩個(gè)比較函數(shù)cmp_stu_by_age和cmp_stu_by_name的實(shí)現(xiàn)。
1. 按年齡比較的函數(shù)
int cmp_stu_by_age(const void *e1, const void *e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}工作原理：
參數(shù)是兩個(gè)void*指針，這是qsort函數(shù)要求的比較函數(shù)格式
將void*指針轉(zhuǎn)換為struct Stu*類型
比較兩個(gè)學(xué)生的年齡字段age
返回兩者的差值
返回值含義：
如果第一個(gè)學(xué)生的年齡小于第二個(gè)學(xué)生，返回負(fù)值
如果兩者年齡相等，返回0
如果第一個(gè)學(xué)生的年齡大于第二個(gè)學(xué)生，返回正值
特點(diǎn)：
簡單直接，適合數(shù)值類型的比較
對(duì)于整數(shù)比較很有效
2. 按姓名比較的函數(shù)
int cmp_stu_by_name(const void *e1, const void *e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}工作原理：
同樣接收兩個(gè)void*指針參數(shù)
將指針轉(zhuǎn)換為struct Stu*類型
使用strcmp函數(shù)比較兩個(gè)學(xué)生的name字符串（后面到字符串部分會(huì)講解）
直接返回strcmp的結(jié)果
返回值含義：
如果第一個(gè)名字在字典序中排在第二個(gè)名字之前，返回負(fù)值
如果兩個(gè)名字相同，返回0
如果第一個(gè)名字在字典序中排在第二個(gè)名字之后，返回正值
特點(diǎn)：
使用標(biāo)準(zhǔn)庫函數(shù)strcmp進(jìn)行字符串比較
遵循字典序（lexicographical order）比較規(guī)則
比較是基于ASCII值的逐個(gè)字符比較
三、qsort函數(shù)的模擬實(shí)現(xiàn)
下面使用回調(diào)函數(shù)和冒泡排序的方式模擬實(shí)現(xiàn)qsort：
#include <stdio.h>
#include <string.h>
// 比較函數(shù)，用于整型比較
int int_cmp(const void *p1, const void *p2)
{
return (*(int*)p1 - *(int*)p2);
}
// 交換函數(shù)，逐字節(jié)交換兩個(gè)元素
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的冒泡排序?qū)崿F(xiàn)
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++) {
// 計(jì)算兩個(gè)要比較元素的地址
void *elem1 = (char*)base + j * size;
void *elem2 = (char*)base + (j + 1) * size;
if (cmp(elem1, elem2) > 0) { // 如果前一個(gè)元素大于后一個(gè)元素
_swap(elem1, elem2, size); // 交換兩個(gè)元素
}
}
}
}
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;
}
這段代碼實(shí)現(xiàn)了一個(gè)通用的冒泡排序函數(shù)，模仿了C標(biāo)準(zhǔn)庫中的qsort函數(shù)的行為。下面我將詳細(xì)解釋各個(gè)部分：
1、比較函數(shù)int_cmp
int int_cmp(const void *p1, const void *p2)
{
return (*(int*)p1 - *(int*)p2);
}這是一個(gè)用于比較整數(shù)的函數(shù)
參數(shù)是兩個(gè)void指針，可以指向任何類型的數(shù)據(jù)
通過強(qiáng)制類型轉(zhuǎn)換(int*)將指針轉(zhuǎn)換為整型指針，然后解引用獲取整數(shù)值
返回值為：
負(fù)數(shù)：如果p1指向的值小于p2指向的值
零：如果兩者相等
正數(shù)：如果p1指向的值大于p2指向的值
2、交換函數(shù)_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;
}
}這個(gè)函數(shù)用于交換兩個(gè)內(nèi)存塊的內(nèi)容
參數(shù)：
p1, p2: 要交換的兩個(gè)內(nèi)存塊的指針
size: 每個(gè)內(nèi)存塊的大小（字節(jié)數(shù)）
實(shí)現(xiàn)方式：
將指針轉(zhuǎn)換為char*（因?yàn)閏har是1字節(jié)）
逐字節(jié)交換兩個(gè)內(nèi)存塊的內(nèi)容
這種實(shí)現(xiàn)方式可以處理任何數(shù)據(jù)類型
3、冒泡排序函數(shù)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);
}
}
}
}這是一個(gè)通用的冒泡排序?qū)崿F(xiàn)
參數(shù)：
base: 數(shù)組的起始地址
count: 數(shù)組中元素的數(shù)量
size: 每個(gè)元素的大?。ㄗ止?jié)數(shù)）
cmp: 比較函數(shù)的指針
實(shí)現(xiàn)要點(diǎn)：
外層循環(huán)控制排序輪數(shù)
內(nèi)層循環(huán)比較相鄰元素
通過(char*)base + j * size計(jì)算元素地址（因?yàn)閏har指針?biāo)阈g(shù)運(yùn)算以字節(jié)為單位）
使用用戶提供的比較函數(shù)來決定是否需要交換
需要交換時(shí)調(diào)用_swap函數(shù)
4、主函數(shù)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;
}創(chuàng)建一個(gè)整型數(shù)組并初始化
計(jì)算數(shù)組大小
調(diào)用bubble_sort進(jìn)行排序，傳入：
數(shù)組地址
元素?cái)?shù)量
每個(gè)元素的大?。╯izeof(int)）
比較函數(shù)int_cmp
打印排序后的數(shù)組
關(guān)于void*指針的說明
在模擬實(shí)現(xiàn)中，我們使用了void*指針，這是C語言中的通用指針類型，可以指向任何類型的數(shù)據(jù)。它的特點(diǎn)包括：
void*指針可以接收任何類型的指針
不能直接對(duì)void*指針進(jìn)行解引用操作
不能對(duì)void*指針進(jìn)行算術(shù)運(yùn)算
使用前需要先轉(zhuǎn)換為具體類型的指針
在排序函數(shù)中，我們通過將void*轉(zhuǎn)換為char*并進(jìn)行指針?biāo)阈g(shù)運(yùn)算來訪問數(shù)組元素，這是因?yàn)?code>char類型的大小為1字節(jié)，可以方便地進(jìn)行字節(jié)級(jí)別的操作。
總結(jié)
到此這篇關(guān)于C語言中qsort函數(shù)使用及其模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)qsort函數(shù)使用及模擬實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
使用C/C++調(diào)用libcurl調(diào)試消息的方式
在使用 C/C++ 調(diào)用 libcurl 進(jìn)行 HTTP 請(qǐng)求時(shí),有時(shí)我們需要查看請(qǐng)求的/應(yīng)答消息的內(nèi)容（包括請(qǐng)求頭和請(qǐng)求體）以方便調(diào)試,libcurl 提供了多種方法來捕獲和輸出這些信息,本文介紹具體的使用方式,需要的朋友可以參考下2025-02-02
這篇文章主要為大家介紹了C語言編程之預(yù)處理過程與define及條件編譯，文中通過圖文及示例代碼方式作了詳細(xì)的解釋，有需要的朋友可以借鑒參考下2021-09-09
C++使用cjson操作Json格式文件(創(chuàng)建、插入、解析、修改、刪除)
本文主要介紹了C++使用cjson操作Json格式文件(創(chuàng)建、插入、解析、修改、刪除),文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
C++通過類實(shí)現(xiàn)控制臺(tái)貪吃蛇
這篇文章主要為大家詳細(xì)介紹了C++通過類實(shí)現(xiàn)控制臺(tái)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C/C++格式化日志庫實(shí)現(xiàn)代碼,需要的朋友可以參考下2019-04-04
深入探索C++中stack和queue的底層實(shí)現(xiàn)
這篇文章主要介紹了C++中的stack和dequeue的底層實(shí)現(xiàn),本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-09-09
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)俄羅斯方塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
select函數(shù)實(shí)現(xiàn)高性能IO多路訪問的關(guān)鍵示例深入解析
這篇文章主要為大家介紹了select函數(shù)實(shí)現(xiàn)高性能IO多路訪問的關(guān)鍵示例深入解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
二叉樹可以簡單理解為對(duì)于一個(gè)節(jié)點(diǎn)來說，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下C中二叉樹與樹的概念和結(jié)構(gòu)，需要的可以參考一下2022-04-04
C++?分割字符串?dāng)?shù)據(jù)的實(shí)現(xiàn)方法
這篇文章主要介紹了C++?分割字符串?dāng)?shù)據(jù)的實(shí)現(xiàn)方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-09-09