前言

這篇文章就是指針進階的收尾環(huán)節(jié)了，相信看過C語言進階——指針（下）的小伙伴一定還記著文章末尾的回調(diào)函數(shù)吧。這篇文章就是借qsort函數(shù)的模擬實現(xiàn)來給小伙伴們展示一下回調(diào)函數(shù)的運用。

1.冒泡排序的實現(xiàn)

在實現(xiàn)qsort函數(shù)，相信有的小伙伴對冒泡排序還存有疑惑，甚至是第一次接觸這個名詞，那么我們就先來講講冒泡排序。

1.1冒泡排序的概念

“冒泡排序（Bubble Sort），是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復(fù)地進行，直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

相信聰明的你已經(jīng)知道了冒泡排序是一種依次比較相鄰元素并按照相應(yīng)規(guī)則進行排序的排序方法。

在這種排序過程中，重要的元素共有兩個，分別是冒泡排序的趟數(shù)以及比較的次數(shù)。一般而言，趟數(shù)是元素的個數(shù)減一得到，為什么不等于元素的個數(shù)呢？因為每進行一趟冒泡排序，就會有一個元素來到它正確的位置，所以當除了最后一個元素以外的其他元素都來到了正確位置的時候，那么最后一個元素也一定處于正確位置。

說完趟數(shù)，再來聊聊比較次數(shù)。有親自實踐的小伙伴們一定發(fā)現(xiàn)了在進行第一趟冒泡排序的時候，比較的次數(shù)是最多的，是除了第一個元素以外的所有元素都要與之比較，也就是元素的個數(shù)減一，但是隨著趟數(shù)的增加，比較的次數(shù)也會隨之減少，究其原因，是因為每經(jīng)過一次冒泡排序，就會有一個元素來到正確的位置，那么這個正確的元素也就無需參加后續(xù)的比較了。

那么具體的代碼實現(xiàn)究竟是怎么樣呢？接下來就讓我們一起揭開它神秘的面紗，一探究竟！

1.2具體代碼的實現(xiàn)

void bubble_sort(int arr[], int sz)
{
	//趟數(shù)
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡排序的過程
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
            }
		}
	}
}

2.qsort函數(shù)

在了解完冒泡排序之后，有的小伙伴還是第一次見到qsort函數(shù)，那么下面我們就來簡單介紹一下qsort函數(shù)。

首先我們要清楚的是qsort函數(shù)是庫里面的函數(shù)，所以我們在使用的時候要引用頭文件<stdlib.h>。

然后我們再來了解一下這個函數(shù)的各個部分。第一個是返回類型，從上圖中我們可以看到返回類型是void，也就是說當我們在引用這個函數(shù)的時候，它并不會返回任何參數(shù)。第二個是參數(shù)部分，第一個參數(shù)是一個指針變量，第二、三個參數(shù)是無符號的整型變量，第四個就是我們之前講解過的函數(shù)指針變量。在第四個參數(shù)部分也就體現(xiàn)了回調(diào)函數(shù)這一功能。

最后我們來講講這個函數(shù)該怎么使用。在引用完頭文件后，我們下一步就是要對這個函數(shù)進行傳參，在意義上分別是要排序的對象，元素個數(shù)，元素大小（以字節(jié)為單位），判斷是否交換的函數(shù)（根據(jù)需求自寫）。

說到第四個參數(shù)所指向的函數(shù)需要根據(jù)需求自己來寫，可能有小伙伴就疑惑了，到底要怎么寫呢。別怕，上面這幅圖片可以說是為我們函數(shù)的書寫提供了方向。首先你要確保你書寫的函數(shù)的返回類型為int，并且依據(jù)交換的原則來進行返回值的代碼書寫。拿整型數(shù)組排序為例，如果你想要最終數(shù)組的整形呈現(xiàn)升序排序，那么如果兩個數(shù)是降序排序就應(yīng)該返回小于0的整型。具體代碼的實現(xiàn)如下，以整形數(shù)組和結(jié)構(gòu)體為例。

//用qsort函數(shù)實現(xiàn)各種類型的排序
//整形數(shù)組的排序
int cmp_int(void const* e1, void const* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int main()
{
	int i = 0;
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, 4, cmp_int);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
//結(jié)構(gòu)體的排序
struct stu
{
	char name[20];
	int  age;
};
int cmp_age(void const*e1, void const*e2)
{
	return (((struct stu*)e1)->age - ((struct stu*)e2)->age);
}
int cmp_name(void const* e1, void const* e2)
{
	return strcmp(((struct stu*)e1)->name ,((struct stu*)e2)->name);
}
int main()
{
	struct stu Stu[3] = { {"zhangsan", 20},{"wangwu", 42},{"lisi",29}};
	int sz = sizeof(Stu) / sizeof(Stu[0]);
	//qsort(Stu, sz, sizeof(Stu[0]), cmp_age);
	qsort(Stu, sz, sizeof(Stu[0]), cmp_name);
	return 0;
}

3.qsort函數(shù)的實現(xiàn)

隨著我們學(xué)習的不斷深入，類型的不斷豐富，我們會發(fā)現(xiàn)上面的冒泡排序已然滿足不了我們的需求，諸如結(jié)構(gòu)體的排序，這種代碼已經(jīng)是無能為力了。那么接下來我們就自己來利用冒泡排序的原理來書寫qsort函數(shù)。

//實現(xiàn)元素的交換
void swap(char* e1, char* e2, size_t sz)
{
	size_t i = 0;
	for (i = 0; i < sz; i++)
	{
		char tmp = 0;
		tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++;
		e2++;
	}
}
//qsort函數(shù)的自定義
void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*e1, const void*e2))
{
	size_t i = 0;
	size_t j = 0;
	//冒泡排序的趟數(shù)
	for (i = 0; i < num-1; i++)
		{
			//比較的次數(shù)
			for (j = 0; j < num - i - 1; j++)
			{
				if (compar((char *)base+j*size,(char*)base+(j+1)*size)>0)
				{
					//交換
					swap((char*)base + j*size, (char*)base + (j + 1)*size, size);
				}
			}
		}
}