C語言庫函數qsort的使用詳解

2022-06-14 10:01:30

一、回撥函數

C語言庫函數中的qsort的是一個回撥函數，回撥函數就是一個通過函數指標呼叫的函數。如果把函數的指標（地址）作為引數傳遞給另一個函數，當這個指標被用來呼叫其所指向的函數時，我們就說這是回撥函數。回撥函數不是由該函數的實現方直接呼叫，而是在特定的事件或條件發生時由另外的一方呼叫的，用於對該事件或條件進行響應。

二、庫函數qsort

void* base：要排序的資料的起始位置

size_t num：待排序資料的元素個數

size_t width：待排序的資料元素的大小，單位是位元組

int(__cdecl*compare)(constvoid*elem1,constvoid*elem2)：把比較函數的地址傳給cmp，e1和e2是要比較的兩個元素的地址。（__cdecl是函數呼叫約定）

注意：最後一個函數引數是一個函數指標，所以在呼叫庫函數qsort()的時候，傳的引數是比較函數的地址。

1、e1小於e2，返回值小於0；

2、e1等於e2，返回0；

3、e1大於e2，返回值大於0。

三、使用qsort排序整型陣列

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

庫函數qsort的比較函數是需要自己實現的，並且已經給定了比較函數的兩個形參。因為e1和e2是無型別指標，不能解除參照和加減。所以此處使用時需要先將指標型別前置型別轉換為int*，再進行解除參照操作。

此處可以加深回撥函數的理解：int_cmp是本人來實現的，當程式執行到qsort函數時，由庫函數qsort對int_cmp進行呼叫。這就是回撥函數。

四、使用qsort排序結構體

1、使用qsort排序結構體中的字元成員

先建立一個學生的結構體型別，定義一個結構體型別的學生陣列，陣列內包含3名學生的資訊。通過qsort函數進行排序。在實現str_name_cmp函數時，需要先將e1和e2先強制型別轉換為struct Stu*型別，由於strcmp函數的返回值剛好契合str_name_cmp函數，可以直接使用return將返回值帶回。通過列印可以發現三名同學已經按ASCII碼完成排序。

2、使用qsort排序結構體中的整型成員

#include <stdlib.h>
#include <stdio.h>
struct Stu
{
	char name[20];
	int age;
};
int str_age_cmp(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
	struct Stu s[] = { {"zhangsan",18},{"lisi",17},{"wangwu",22} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), str_age_cmp);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", s[i].age);//輸出17 18 22
	}
	return 0;
}

排序結構體整型成員和排序整型陣列、結構體字元成員方式相似。

五、基於氣泡排序的庫函數qsort的模擬實現

1、使用改寫函數排序整型陣列

#include <stdlib.h>
#include <stdio.h>
int int_cmp(const void* e1, const void* e2)//比較函數
{
	return *(int*)e1 - *(int*)e2;//升序排序
}
Swap(char* p1, char* p2, size_t width)
{
	for (int i = 0; i < width; i++)//每個位元組交換
	{
		int tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void qsort_bubble(void* base, size_t sz, size_t width, int(* compare)(const void* e1, const void* e2))
{//基於庫函數qsort進行改寫的氣泡排序
	for (int i = 0; i < sz-1; i++)
	{
		int change = 0;
		for (int j = 1; j < sz - i; j++)
		{
            //交換
			if (compare((char*)base+(j-1)*width , (char*)base+j*width)>0)
			{
				Swap((char*)base + (j - 1) * width, (char*)base + j * width,width);
				change = 1;
			}
		}
		if (change == 0)
			break;
	}
}
int main()
{
	int arr[10] = { 9,8,7,6,5,2,4,3,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort_bubble(arr, sz,sizeof(arr[0]),int_cmp);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

qsort_bubble函數中，採用氣泡排序的比較方式，形參模仿庫函數qsort中的形參。

在函數內部呼叫compare時(compare是比較函數的地址)，由於外部比較的資料型別不可知，故使用最小內建型別char和資料型別的長度width來表示外部型別所佔位元組。

2、使用改寫函數排序結構體中的字元成員

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct Stu//定義結構體
{
	char name[20];
	int age;
};
int str_name_cmp(const void* e1, const void* e2)//字元的比較函數
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
Swap(char* p1, char* p2, size_t width)//交換函數
{
	for (int i = 0; i < width; i++)
	{
		int tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void qsort_bubble(void* base, size_t sz, size_t width, int(*compare)(const void* e1, const void* e2))
{基於庫函數qsort進行改寫的氣泡排序
	for (int i = 0; i < sz - 1; i++)
	{
		int change = 0;
		for (int j = 1; j < sz - i; j++)
		{
			if (compare((char*)base + (j - 1) * width, (char*)base + j * width)>0)
			{
				Swap((char*)base + (j - 1) * width, (char*)base + j * width, width);
				change = 1;
			}
		}
		if (change == 0)
			break;
	}
}
int main()
{
	struct Stu s[] = {{"zhangsan",18},{"lisi",17},{"wangwu",22}};
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), str_name_cmp);
	for (int i = 0; i < sz; i++)
	{
		printf("%s ", s[i].name);
	}
	return 0;
}

輸出結果lisi wangwu zhangsan，理解方式和上方例子一樣。

3、對庫函數qsort的總結

第一次使用庫函數qsort的時候，肯定會疑惑，為什麼e1-e2的返回值大於0時，升序排序；反之降序？

我們在模擬實現的時候，在氣泡排序內部呼叫compare這個函數地址，傳參時，如果前一個元素的值大於後一個元素，那麼傳入比較函數，e1-e2＞0，進行交換，交換完畢後e1<e2，實現了升序排序！

如果要實現降序排序，在比較函數內使用e2-e1即可，意思是後一個元素大於前一個元素，進行交換，交換完畢後e1>e2，實現了降序排序！

六、力扣977#中庫函數qsort的使用

使用pow函數對陣列元素逐個平方。由於素組記憶體在負數，所以平方後陣列可能亂序，需要重新排序，這裡可以使用庫函數qsort進行排序。

 int compare(const void* elem1,const void* elem2)//比較函數
 {
     return *(int*)elem1-*(int*)elem2;
 }
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=pow(nums[i],2);
    }
    qsort(nums,numsSize,sizeof(nums[0]),compare);//庫函數qsort的使用
    return nums;
}

但是平常刷題是還是不建議無腦上qsort，需要根據題目要求合理的選擇排序演演算法。

到此這篇關於C語言庫函數qsort的使用的文章就介紹到這了,更多相關C語言庫函數qsort內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！