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

2023-02-09 06:01:42

一、前言

我們初識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為每個元素的寬度，單位為位元組，是一個無符號整型，所以我們傳一個無符號整型。圖六說明這個函數指標指向一個含有兩個空指標作為引數並且返回型別為int的（比較）函數。這個是qsort的最後一個引數，作用是讓我們提供比較大小的規則，所以我們傳的時候需要傳一個函數地址讓庫函數中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函數並不知道你要傳的是什麼型別，也就是它使用這個函數時不知道傳什麼型別的實參，所以統一先傳一個空型別地址然後函數用空型別指標接收。
3.空指標是什麼意思，怎麼用？
空指標就像一個垃圾桶，我們可以對其賦上任意型別的指標，這很方便，但是它不能直接使用，就像我們賦的時候一樣，用的時候它並不知道你是什麼型別，它相當於只儲存了一個位元組的地址，沒有明確的步長（指標+1跳過的位元組）和存取許可權大小（解除參照指標存取的位元組個數）。所以當我們用空指標時，需要進行強制型別轉換，轉換成我們需要的型別。
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的介紹，你會發現他們很相似，qsort中用到的回撥函數也是需要返回這樣的形式。

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

你對於qsort內部如何執行操作的是否感興趣呢？你對於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，然後根據指標加幾就跳過幾個步長個位元組來確定每次跳過一個元素。
2.在my_qsort函數中，我們的swap函數也是一個重要部分，它是如何實現的呢？
☃️首先和1剛開始一樣，我們傳的實參的形式就是為了保證每次可以跳過一個元素，然後當傳到swap函數裡後，我們不像cmp函數一樣有提前準備好的強轉型別，因此我們需要用一種特別的方法保證可以互換元素，那麼我們會想到元素是怎樣儲存的呢，是以二進位制以位元組為單位儲存的，那麼我們如果需要交換元素，是不是隻需要把每個位元組都交換一次就好了呢？答案是肯定的，於是我們也將傳來的地址強制型別轉換為char*，保證每次交換的是一個位元組，然後又有一個問題就是我們需要交換幾次呢，還記得之前傳的那個引數width嗎，它是每個元素的寬度，單位是位元組，因此我們可以通過一個for迴圈，修女換width次來使得一個元素所佔的位元組全部交換。

我們這一部分雖然是用模擬的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;
}

回撥函數：回撥函數就是一個通過函數指標呼叫的函數。如果你把函數指標（地址）作為引數傳遞給另一個函數，當這個指標被用來呼叫其所指向的函數時，我們就說這是回撥函數。回撥函數不是由該函數的實現方直接呼叫，而是在特定的事件或條件發生時由另外一方呼叫的，用於對該事件或條件進行響應。
通常來講就是：把這個函數地址作為引數傳過去，另一個函數用函數指標接收然後再呼叫這個函數，那麼這個被呼叫的函數就叫回撥函數。（通過函數指標呼叫的這個函數，叫做回撥函數）