C語(yǔ)言中qsort函數(shù)使用及其模擬實(shí)現(xiàn)教程
一、qsort函數(shù)簡(jiǎn)介
qsort是C標(biāo)準(zhǔn)庫(kù)中的一個(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)庫(kù)規(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是庫(kù)函數(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)庫(kù)中的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)：
簡(jiǎ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)庫(kù)函數(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)庫(kù)中的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語(yǔ)言中的通用指針類型，可以指向任何類型的數(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語(yǔ)言中qsort函數(shù)使用及其模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)qsort函數(shù)使用及模擬實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
類和對(duì)象是兩種以計(jì)算機(jī)為載體的計(jì)算機(jī)語(yǔ)言的合稱。對(duì)象是對(duì)客觀事物的抽象，類是對(duì)對(duì)象的抽象。類是一種抽象的數(shù)據(jù)類型；變量就是可以變化的量，存儲(chǔ)在內(nèi)存中—個(gè)可以擁有在某個(gè)范圍內(nèi)的可變存儲(chǔ)區(qū)域2022-05-05
這篇文章主要介紹了C++智能指針實(shí)例詳解,需要的朋友可以參考下2014-07-07
C++?棧和隊(duì)列的實(shí)現(xiàn)超詳細(xì)解析
棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為?"一對(duì)一"?的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解2022-03-03
C語(yǔ)言中send()函數(shù)和sendto()函數(shù)的使用方法
這篇文章主要介紹了C語(yǔ)言中send()函數(shù)和sendto()函數(shù)的使用方法,是C語(yǔ)言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
在C程序執(zhí)行過程中，其值不發(fā)生改變的量稱為常量，其值可變的量稱為變量，本文將帶你了解什么是常量和變量，以及使用方法，需要的朋友可以參考下2023-05-05
Clion是一款專門開發(fā)C以及C++所設(shè)計(jì)的跨平臺(tái)的IDE，本文給大家介紹Clion調(diào)試ROS包的方法，感興趣的朋友跟隨小編一起看看吧2021-07-07
模板是C++最重要的設(shè)計(jì)。這篇文章講的是函數(shù)模板,只是簡(jiǎn)單介紹模板的一些功能,關(guān)于模板的更多的內(nèi)容會(huì)在類模板中詳細(xì)介紹。文章還著重介紹了重載解析過程2022-08-08
這篇文章主要介紹了C/C++?extern和static的使用,在講到extern和static的時(shí)候先了解一下定義和聲明的基本概念，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-06-06
本文主要介紹了C語(yǔ)言堆實(shí)現(xiàn)建堆算法和堆排序,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-09-09
在 C 語(yǔ)言中,ferror() 是一個(gè)內(nèi)置函數(shù),用于在文件操作期間檢查文件是否發(fā)生錯(cuò)誤,它提供了一種簡(jiǎn)單的方法,在你的 C 程序中進(jìn)行文件操作時(shí)不會(huì)中斷,本文給大家介紹了C語(yǔ)言中文件操作Error處理的方法,需要的朋友可以參考下2025-10-10