【指針進階三】實現C語言快排函數qsort＆回調函數

0. 經典快速排序算法-Quick_sort

先來手動實現一下Quick_sort 排序函數

#include<stdio.h>
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	int meeti = left;
	Swap(&arr[keyi], &arr[meeti]);

	Quick_sort(arr, begin, meeti-1);
	Quick_sort(arr, meeti+1, end);
	
}

void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Quick_sort(arr, 0,sz-1);
	Print(arr, sz);
	return 0;
}

排序結果：

 

 

但是這裏有一個問題: 如果下次我想對一個結構體進行排序，我對這個排序算法的改動就會非常大（幾乎每一處都有改動），下面我也給出排序結構體相應的代碼實現，給各比特看看。

#include<stdio.h>
#include<string.h>
typedef struct stu
{
	char name[20];
	int age;
}stu;

void Swap(stu* a,stu* b)
{
	stu temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(stu* ps, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
		{
			right--;
		}
		while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
		{
			left++;
		}
		Swap(&ps[left], &ps[right]);
	}
	int meeti = left;
	Swap(&ps[keyi], &ps[meeti]);

	Quick_sort(ps, begin, meeti - 1);
	Quick_sort(ps, meeti+1, end);
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}

int main()
{
	stu s[3] = { {"張三",18},{"李四",20},{"王五",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	Quick_sort(s,0,sz-1);
	Print(s, sz);
	return 0;
}

排序結果：

 

 由此我們就想：能不能設計出一個函數使得在給不同數據類型的元素進行排序時能够增加排序函數Quick_sort代碼的複用性，因此，庫函數qsort應運而生 ，那這個函數長什麼樣子呐？

1. qsort排序函數的基本介紹

qsort排序函數是C語言標准庫裏的函數,實現原理是快速排序算法,函數原型如下:

 qsort函數的相關參數的介紹和意義:

• 頭文件: #include<stdlib.h>
• 返回值: 無
• void  base: 待排序數據元素的起始地址
• size_t num:  待排序數據元素的個數
• size_t width:待排序數據元素所占的大小,單比特是字節
• int( * cmp)(const void*,const void*): 函數指針-比較數據元素大小的函數,排序依據

舉個例子: 

#include<stdio.h>
#include<stdlib.h>
//以qsort庫函數實現整型數組排序為例
int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp);
	//arr:數組名,也是數組首元素的地址,數值上等於首元素中4個字節中地址最低的那個字節的地址
	//sz:數組arr的元素個數
	//sizeof(arr[0]):每一個數組元素所占的字節數
	//cmp_int:回調函數-比較數組元素的函數,根據調用者的需要自行實現
	Print(arr, sz);
	return 0;
}

先拋去qsort函數具體實現不談，看到這裏，你就知道了qsort函數的靈活性在於第四個參數（比較函數）是可以根據使用者的具體排序要求來自行設計。

2. 比較函數

比較函數的設計舉例：整型數組，結構體數組等等

整型數組排序：（全部代碼）

擔心你看花函數之間的調用關系：給你個圖理解一下

 

#include<stdio.h>
#include<stdlib.h>

int cmp_int(const void* e1, const void* e2)
{
    //比較兩個整型元素
	//void*是無具體類型的指針
	//void*的指針可以接收任意類型的地址,類似垃圾桶
	//void*的指針沒有具體類型,不能+1-1(因為不知道加多少)

	//昇序:
	return *(int*)e1 - *(int*)e2;

	//降序:
	//return *(int*)e2 - *(int*)e1;
}


void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

void test1()
{
	int arr[6] = { 14,35,4,42,6,12 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
	Print(arr, sz);
}


int main()
{
	test1();

	return 0;
}

由於void空類型的指針：

• 可以接收任何類型的指針
• 不能直接加减整數，使用前需要强轉 

因為cmp比較函數需要使用者自行設計，所以對於不同的使用者在qsort函數裏傳給cmp函數的參數類型可能是任何類型的指針，所以在cmp比較函數內得用void*類型的指針來接收，使用時只需將void* 類型的指針做出相應的强轉即可。

排序結果：

 

 

結構體數組排序：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct stu
{
	char name[20];
	int age;
}stu;

int cmp_struct_by_name(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);//妙哉之處
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}


void test2()
{
	stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
	Print(s, sz);
}

int main()
{
	test2();

	return 0;
}

排序結果：

比較字符串用strcmp函數，頭文件#include<string.h> 

• 妙哉之處：strcmp比較函數和規定的cmp比較函數的返回值的意義相同
• 返回值>0             elem1>elem2
• 返回值==0           elem1==elem2
• 返回值<0             elem1<elem2

 2. qsort函數的具體實現

學習qsort函數的具體實現，你將學到這個C語言庫函數另一個絕妙的地方。

void Swap(char* buff1,char* buff2,int width)
{
	if (buff1 != buff2)
	{
		//way1
		//while (width--)
		//{
		//	char temp = *buff1;
		//	*buff1 = *buff2;
		//	*buff2 = temp;
		//	buff1++;
		//	buff2++;
		
		//way2
		for (int i = 0; i < width; i++)
		{
			char temp = *(buff1+i);
	        *(buff1+i) = *(buff2+i);
	        *(buff2+i) = temp;
		}
	}
}

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
	int flag = 1;
	//趟數
	for (int i = 0; i < sz-1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (cmp_struct_by_name((char*)base + j * width, (char*)base + (j+1) * width)>0)
			{
				Swap((char*)base + j * width, (char*)base + (j+1) * width, width);
				flag = 0;
			}
		}
		if (flag == 1) break;
	}
}

巧妙之處在於將實際參數void* 類型的base指針强轉為char*類型。

類比int arr[5]={34,5,35,62,1};
Print(arr,5),這裏的arr其實就是首元素的地址，在數值上和首元素4個字節中最低字節的地址是相同的，所以cmp函數的參數即使是char* 一個字節的地址，在cmp函數內同樣可以强轉為所需要的類型，進行解引用，拿到相應的字節數進行比較，這樣就能做到在bubble_sort函數內得到統一，所以無論我們要對任何類型的數據進行排序，都可以直接調用bubble_sort函數，只需要更改cmp函數即可，這就增加了bubble_sort函數代碼的複用性。