C語言中qsort函數(shù)使用及其模擬實現(xiàn)教程
一、qsort函數(shù)簡介
qsort是C標準庫中的一個快速排序函數(shù)，位于stdlib.h頭文件中。它的原型如下：
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
參數(shù)說明
base: 指向要排序數(shù)組的第一個元素的指針
nitems: 數(shù)組中元素的個數(shù)
size: 數(shù)組中每個元素的大小（以字節(jié)為單位）
compar: 用于比較兩個元素的函數(shù)指針
二、qsort使用示例
1、使用qsort排序整型數(shù)據(jù)
#include <stdio.h>
#include <stdlib.h> // 需要包含stdlib.h以使用qsort
// qsort函數(shù)的使用者需要實現(xiàn)一個比較函數(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ī)則：
接受兩個const void*參數(shù)（指向要比較元素的指針）
返回一個int值表示比較結(jié)果：
負數(shù)：第一個參數(shù)小于第二個參數(shù)
零：兩個參數(shù)相等
正數(shù)：第一個參數(shù)大于第二個參數(shù)
2. 為什么使用const void*參數(shù)
通用性：
void*可以指向任何數(shù)據(jù)類型，使qsort能處理各種類型的數(shù)組安全性：
const修飾確保函數(shù)不會修改原始數(shù)據(jù)標準化：這是C標準庫規(guī)定的接口形式
3. 具體實現(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ù)值
比較運算：a - b的結(jié)果：
若a > b → 結(jié)果為正 → 表示a應(yīng)該在b后面（升序）
若a == b → 結(jié)果為0 → 表示兩者相等
若a < b → 結(jié)果為負 → 表示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
計算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 { // 學生結(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ù)，專門用來比較兩個字符串的大小
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標準庫中的qsort函數(shù)對結(jié)構(gòu)體數(shù)組進行排序，重點在于兩個比較函數(shù)cmp_stu_by_age和cmp_stu_by_name的實現(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ù)是兩個void*指針，這是qsort函數(shù)要求的比較函數(shù)格式
將void*指針轉(zhuǎn)換為struct Stu*類型
比較兩個學生的年齡字段age
返回兩者的差值
返回值含義：
如果第一個學生的年齡小于第二個學生，返回負值
如果兩者年齡相等，返回0
如果第一個學生的年齡大于第二個學生，返回正值
特點：
簡單直接，適合數(shù)值類型的比較
對于整數(shù)比較很有效
2. 按姓名比較的函數(shù)
int cmp_stu_by_name(const void *e1, const void *e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}工作原理：
同樣接收兩個void*指針參數(shù)
將指針轉(zhuǎn)換為struct Stu*類型
使用strcmp函數(shù)比較兩個學生的name字符串（后面到字符串部分會講解）
直接返回strcmp的結(jié)果
返回值含義：
如果第一個名字在字典序中排在第二個名字之前，返回負值
如果兩個名字相同，返回0
如果第一個名字在字典序中排在第二個名字之后，返回正值
特點：
使用標準庫函數(shù)strcmp進行字符串比較
遵循字典序（lexicographical order）比較規(guī)則
比較是基于ASCII值的逐個字符比較
三、qsort函數(shù)的模擬實現(xiàn)
下面使用回調(diào)函數(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é)交換兩個元素
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++) {
// 計算兩個要比較元素的地址
void *elem1 = (char*)base + j * size;
void *elem2 = (char*)base + (j + 1) * size;
if (cmp(elem1, elem2) > 0) { // 如果前一個元素大于后一個元素
_swap(elem1, elem2, size); // 交換兩個元素
}
}
}
}
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;
}
這段代碼實現(xiàn)了一個通用的冒泡排序函數(shù)，模仿了C標準庫中的qsort函數(shù)的行為。下面我將詳細解釋各個部分：
1、比較函數(shù)int_cmp
int int_cmp(const void *p1, const void *p2)
{
return (*(int*)p1 - *(int*)p2);
}這是一個用于比較整數(shù)的函數(shù)
參數(shù)是兩個void指針，可以指向任何類型的數(shù)據(jù)
通過強制類型轉(zhuǎn)換(int*)將指針轉(zhuǎn)換為整型指針，然后解引用獲取整數(shù)值
返回值為：
負數(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;
}
}這個函數(shù)用于交換兩個內(nèi)存塊的內(nèi)容
參數(shù)：
p1, p2: 要交換的兩個內(nèi)存塊的指針
size: 每個內(nèi)存塊的大?。ㄗ止?jié)數(shù)）
實現(xiàn)方式：
將指針轉(zhuǎn)換為char*（因為char是1字節(jié)）
逐字節(jié)交換兩個內(nèi)存塊的內(nèi)容
這種實現(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);
}
}
}
}這是一個通用的冒泡排序?qū)崿F(xiàn)
參數(shù)：
base: 數(shù)組的起始地址
count: 數(shù)組中元素的數(shù)量
size: 每個元素的大小（字節(jié)數(shù)）
cmp: 比較函數(shù)的指針
實現(xiàn)要點：
外層循環(huán)控制排序輪數(shù)
內(nèi)層循環(huán)比較相鄰元素
通過(char*)base + j * size計算元素地址（因為char指針算術(shù)運算以字節(jié)為單位）
使用用戶提供的比較函數(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)建一個整型數(shù)組并初始化
計算數(shù)組大小
調(diào)用bubble_sort進行排序，傳入：
數(shù)組地址
元素數(shù)量
每個元素的大?。╯izeof(int)）
比較函數(shù)int_cmp
打印排序后的數(shù)組
關(guān)于void*指針的說明
在模擬實現(xiàn)中，我們使用了void*指針，這是C語言中的通用指針類型，可以指向任何類型的數(shù)據(jù)。它的特點包括：
void*指針可以接收任何類型的指針
不能直接對void*指針進行解引用操作
不能對void*指針進行算術(shù)運算
使用前需要先轉(zhuǎn)換為具體類型的指針
在排序函數(shù)中，我們通過將void*轉(zhuǎn)換為char*并進行指針算術(shù)運算來訪問數(shù)組元素，這是因為char類型的大小為1字節(jié)，可以方便地進行字節(jié)級別的操作。
總結(jié)
到此這篇關(guān)于C語言中qsort函數(shù)使用及其模擬實現(xiàn)的文章就介紹到這了,更多相關(guān)qsort函數(shù)使用及模擬實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
類和對象是兩種以計算機為載體的計算機語言的合稱。對象是對客觀事物的抽象，類是對對象的抽象。類是一種抽象的數(shù)據(jù)類型；變量就是可以變化的量，存儲在內(nèi)存中—個可以擁有在某個范圍內(nèi)的可變存儲區(qū)域2022-05-05
這篇文章主要介紹了C++智能指針實例詳解,需要的朋友可以參考下2014-07-07
棧和隊列，嚴格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關(guān)系為?"一對一"?的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨作為一章，做重點講解2022-03-03
C語言中send()函數(shù)和sendto()函數(shù)的使用方法
這篇文章主要介紹了C語言中send()函數(shù)和sendto()函數(shù)的使用方法,是C語言入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
在C程序執(zhí)行過程中，其值不發(fā)生改變的量稱為常量，其值可變的量稱為變量，本文將帶你了解什么是常量和變量，以及使用方法，需要的朋友可以參考下2023-05-05
Clion是一款專門開發(fā)C以及C++所設(shè)計的跨平臺的IDE，本文給大家介紹Clion調(diào)試ROS包的方法，感興趣的朋友跟隨小編一起看看吧2021-07-07
模板是C++最重要的設(shè)計。這篇文章講的是函數(shù)模板,只是簡單介紹模板的一些功能,關(guān)于模板的更多的內(nèi)容會在類模板中詳細介紹。文章還著重介紹了重載解析過程2022-08-08
這篇文章主要介紹了C/C++?extern和static的使用,在講到extern和static的時候先了解一下定義和聲明的基本概念，本文通過實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2022-06-06
本文主要介紹了C語言堆實現(xiàn)建堆算法和堆排序,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-09-09
在 C 語言中,ferror() 是一個內(nèi)置函數(shù),用于在文件操作期間檢查文件是否發(fā)生錯誤,它提供了一種簡單的方法,在你的 C 程序中進行文件操作時不會中斷,本文給大家介紹了C語言中文件操作Error處理的方法,需要的朋友可以參考下2025-10-10