你真的理解C語言qsort函數嗎?帶你深度剖析qsort函數

更新時間：2023年02月07日 16:02:18 作者：大魔王不哭

這篇文章主要介紹了你真的理解C語言qsort函數嗎?帶你深度剖析qsort函數,本篇將引入一個庫函數來實現我們希望的順序，結合示例代碼給大家介紹的非常詳細，需要的朋友可以參考下

一、前言

我們初識C語言時，會做過讓一個整型數組按照從小到大來排序的問題，我們使用的是冒泡排序法，但是如果我們想要比較其他類型怎么辦呢，顯然我們當時的代碼只適用于簡單的整形排序，對于結構體等沒辦法排序，本篇將引入一個庫函數來實現我們希望的順序。

二、簡單冒泡排序法

#include <stdio.h>
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int i = 0;
	int sz = sizeof(arr);
	for (i = 0; i < sz-1; i++)
	{
		int j = 0;
		for (j = 0; j < sz-1-i; j++)
		{
			int tep = 0;
			if (arr[j] > arr[j + 1])
			{
				tep = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tep;
			}
		}
	}
	return 0;
}

這是我們最初學習的冒泡排序法，我們如果把其修改一下，能不能比較其它類型的數據呢，結果是肯定的。

三、qsort函數的使用

1、qsort函數的介紹

圖片1為整體描述，下面的圖片2、3、4、5、6為圖片1的解釋。

首先我們可以看出qsort函數不需要返回類型，有四個參數，分別為空指針、無符號型、無符號型、函數指針。圖二說明該函數無返回類型。圖三說明我們base為要排序中的起始地址，是一個空指針類型，所以我們傳首元素地址。圖四說明num為元素個數，是一個無符號整型，所以我們傳一個無符號整型。圖五說明width為每個元素的寬度，單位為字節(jié)，是一個無符號整型，所以我們傳一個無符號整型。圖六說明這個函數指針指向一個含有兩個空指針作為參數并且返回類型為int的（比較）函數。這個是qsort的最后一個參數，作用是讓我們提供比較大小的規(guī)則，所以我們傳的時候需要傳一個函數地址讓庫函數中qsort的函數指針來接收。補充：qsort對應的頭文件為<stdlib.h>。（比較）函數中的兩個參數如果第一個大返回一個大于0的數，如果第二個大返回一個小于0的數，如果相等則返回0。

看完這些，相信你對qsort函數有了初步了解。

2、qsort函數的運用

在這里我們舉出兩個例子來直觀看出qsort的應用方法，分別為整型數組排序和結構體排序。

2.1、qsort函數排序整型數組

#include<stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for(i = 0;i<sz;i++)
	printf("%d ", arr[i]);
}

在這里插入圖片描述

這樣就完成了排序。

疑問：
1.qsort第四個參數（函數地址）為什么不需要傳參？
首先：我們要知道，我們第四個參數傳的是一個函數地址（函數名加不加取地址符號都可以表示函數的地址），而不是一個函數，所以就沒有傳參這個說法。其次：等到庫函數qsort用函數指針接收后會進行傳參等工作（這是程序內部進行的，我們不需要管）。
2.為什么函數定義里面的參數是空指針類型，而不是特定類型？
因為qsort函數并不知道你要傳的是什么類型，也就是它使用這個函數時不知道傳什么類型的實參，所以統(tǒng)一先傳一個空類型地址然后函數用空類型指針接收。
3.空指針是什么意思，怎么用？
空指針就像一個垃圾桶，我們可以對其賦上任意類型的指針，這很方便，但是它不能直接使用，就像我們賦的時候一樣，用的時候它并不知道你是什么類型，它相當于只儲存了一個字節(jié)的地址，沒有明確的步長（指針+1跳過的字節(jié)）和訪問權限大?。ń庖弥羔樤L問的字節(jié)個數）。所以當我們用空指針時，需要進行強制類型轉換，轉換成我們需要的類型。
4.為什么com_int函數在用的時候要把參數強轉為int？
因為當我們使用qsort函數時，我們肯定知道要進行排序的類型，所以我們需要根據自己的需要的類型來寫出對應的函數讓qsort函數調用。

2.2、qsort函數排序結構體

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stu
{
	char name[10];
	int age;
};
//排序結構體年齡的回調函數
int cmp_struct_stu_age(const void*e1,const void*e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
//排序結構體姓名的回調函數
int cmp_struct_stu_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e1)->name);
}
//運用qsort函數排序結構體年齡
void test1()
{
	struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
//運用qsort函數排序結構體名字
void test2()
{
	struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
}
int main()
{
	test1();
	//test2();
	return 0;
}

補充：
字符串比較大小使用strcmp函數，對應的頭文件為<string.h>，依次從左到右比較字母的ASCII值直到不相等，左邊大返回大于0的數，右邊大返回小于0的數，直到最后都相等返回0，如果你仔細看了最前面關于qsort的介紹，你會發(fā)現他們很相似，qsort中用到的回調函數也是需要返回這樣的形式。

四、利用冒泡排序模擬實現qsort函數

你對于qsort內部如何執(zhí)行操作的是否感興趣呢？你對于qsort中傳的那些參數是否存在疑問，不知道他們有什么作用呢，接著看下面的內容，讓我們更進一步理解qsort的工作原理，同時讓你的冒泡排序變得具有普遍性。

首先我們先試著用my_qsort函數模擬出qsort函數來對一個整型數組排序。

#include <stdio.h>
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++, buf1++, buf2++)
	{
		char tep = 0;
		tep = *buf1;
		*buf1 = *buf2;
		*buf2 = tep;
	}
}
void my_qsort(const void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)
			swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
		}
	}
}
void test3()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
		printf("%d ", arr[i]);
}
int main()
{
	test3();
	return 0;
}

以上代碼就是我們模擬出的qsort函數，相信看完這個你會對qsort理解更深刻，不過有一點需要注意，我們模擬時使用的是冒泡排序，而qsort其實內部使用的是快排，所以其實稍有差距。但大體是一致的。

補充：
1.在my_qsort函數中，我們在比較函數（cmp）中傳入的是內容解釋：
??(char*)base+jwidth 這個實際上就是原始的base是空指針類型，所以我們無法直接使用，但我們也不確定傳來的具體是什么類型，因此我們先將其強制類型轉換為char，然后根據指針加幾就跳過幾個步長個字節(jié)來確定每次跳過一個元素。
2.在my_qsort函數中，我們的swap函數也是一個重要部分，它是如何實現的呢？
??首先和1剛開始一樣，我們傳的實參的形式就是為了保證每次可以跳過一個元素，然后當傳到swap函數里后，我們不像cmp函數一樣有提前準備好的強轉類型，因此我們需要用一種特別的方法保證可以互換元素，那么我們會想到元素是怎樣儲存的呢，是以二進制以字節(jié)為單位儲存的，那么我們如果需要交換元素，是不是只需要把每個字節(jié)都交換一次就好了呢？答案是肯定的，于是我們也將傳來的地址強制類型轉換為char*，保證每次交換的是一個字節(jié)，然后又有一個問題就是我們需要交換幾次呢，還記得之前傳的那個參數width嗎，它是每個元素的寬度，單位是字節(jié)，因此我們可以通過一個for循環(huán)，修女換width次來使得一個元素所占的字節(jié)全部交換。

我們這一部分雖然是用模擬的qsort來排序整型數組，但其實如果這個學會了的話，結構體和前面說的是一模一樣的，因為模擬的qsort不用變，只需要改一下cmp函數的類型即可。

完整代碼如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//排序整型數組順序時的回調函數
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
//聲明結構體類型
struct stu
{
	char name[10];
	int age;
};
//排序結構體年齡順序時的回調函數
int cmp_struct_stu_age(const void*e1,const void*e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
//排序結構體名字順序時的回調函數
int cmp_struct_stu_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e1)->name);
}
//運用qsort函數排序整型數組
void test1()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
}
//運用qsort函數排序結構體
void test2()
{
	struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
	//qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
//模擬qsort中的交換函數
void swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++, buf1++, buf2++)
	{
		char tep = 0;
		tep = *buf1;
		*buf1 = *buf2;
		*buf2 = tep;
	}
}
//模擬qsort
void my_qsort(const void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)
			swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
		}
	}
}
//運用模擬qsort函數(my_qsort)排序整型數組
void test3()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
		printf("%d ", arr[i]);
}
//運用模擬qsort函數(my_qsort)排序結構體
void test4()
{
	struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	my_qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
	//qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
int main()
{
	//test1();  //用qsort實現整型數組排序
	//test2();  //用qsort實現結構體排序
	test3();    //用模擬qsort函數實現整型數組排序
	//test(4)   //用模擬qsort函數實現結構體排序
	return 0;
}

回調函數：回調函數就是一個通過函數指針調用的函數。如果你把函數指針（地址）作為參數傳遞給另一個函數，當這個指針被用來調用其所指向的函數時，我們就說這是回調函數?；卣{函數不是由該函數的實現方直接調用，而是在特定的事件或條件發(fā)生時由另外一方調用的，用于對該事件或條件進行響應。
通常來講就是：把這個函數地址作為參數傳過去，另一個函數用函數指針接收然后再調用這個函數，那么這個被調用的函數就叫回調函數。（通過函數指針調用的這個函數，叫做回調函數）