C語言庫函數qsort及bsearch快速排序演演算法使用解析

2022-02-14 13:00:13

qsort

qsrot 就是C語言庫函數中的快速排序函數，對陣列，結構體都可以實現快速排序，他在標頭檔案<stdlib.h>中使用，宣告格式為:

void qsort(void* base, size_t nums, size_t size, int (*compare)(const void *, const void*))

這麼煩人一長串的引數各是什麼意思呢，base 是指向要排序的陣列的第一個元素的指標。nums是由 base 指向的陣列中元素的個數。size 是陣列中每個元素的大小，以位元組為單位。compare 是用來比較兩個元素的函數，這個比較函數需要我們自己補全。

含義

void*代表著任意型別的陣列，這個陣列也就是我們想用來排序的物件陣列；size_t 在系統裡面被定義成 int 型別的，所以我們可以把 size_t修飾的數預設為一個整數。

為什麼要細化出陣列大小和元素大小？這和我排序有毛關係？其實這是為了區分不同型別的陣列，int 和 char 型別的陣列每個元素所佔空間就不一樣，自然要區別開。

int main()
{
	int arr[6] = { 1,4,5,8,2,3};
	qsort(arr, 6, sizeof(arr[0]), compare);
}

最後的 compare 函數我是直接將這個元素作為引數傳進來，那麼問題來了,這個比較函數怎麼寫？

我們根本不用管那個 *compare 的指標什麼鬼，他就相當於告訴你這裡在用一個外部函數，我們只要明白整個函數名兒上去就是妥妥的了，這個函數名不一定就叫 compare ，諸君自便。

實現

後面的（const void , const void)自然就是這個函數的引數了，兩個 void* 實際運用的時候就看成 a ，b，既然是外部函數我們就要自己動手了,我們的最終目的是為了排序，比較函數就應該實現陣列元素大小的比較，本質上說就是在比較 a和b 的大小，而a，b是我陣列中任意的兩兩元素。

那首先要做的就是把這個不知道什麼型別的 void 指標變成我們給定的，之前程式碼中給的是整型陣列，這裡就要對應變成整型指標，這兩個指標指向陣列中的兩個整數，既然要比較，我們就直接做減法看正負即可，把這兩個指標轉換成真正的整數後就大功告成了：

	int* p = (int*)a;
	int* q = (int*)b;
	int c = *p;
	int d = *q;

成品如下：

#include<stdlib.h>
int compare(const void* a,const void* b)
{
	int* p = (int*)a;
	int* q = (int*)b;
	int c = *p;
	int d = *q;
	return c - d;
}
int main()
{
	int i = 0;
	int arr[6] = { 1,4,5,8,2,3 };
	qsort(arr, 6, sizeof(arr[0]), compare);
	for (i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

結果如下

結構體的排序也是同理，如下：

#include<stdlib.h>
int compare(const void* a,const void* b)
{
	int* p = (int*)a;
	int* q = (int*)b;
	int c = *p;
	int d = *q;
	return c - d;
}
int main()
{
	int i = 0;
	int arr[6] = { 1,4,5,8,2,3 };
	qsort(arr, 6, sizeof(arr[0]), compare);
	for (i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

結果就是根據結構體中 a 成員大小來排的：

格局開啟

1.上面是實現從小到大排列，要實現從大到小排只需 return d - c 即可。
2.如果是比較浮點數，注意在兩個數相差不大時，介於（-1，1），因為現在是整型指標，返回值也是整型，return 回來的就是個 0，造成無意義操作，怎麼處理呢？很簡單，改成如下即可：

int compare(const void* a,const void* b)
{
	int* p = (int*)a;
	int* q = (int*)b;
	int c = *p;
	int d = *q;
	if(c - d<0)
	{
	return -1;
	}
	else
	{
	return 1;
	}
}

bsearch

bsearch （binary search）也是C語言庫函數，功能是執行二分查詢，宣告定義如下

void *bsearch(const void *key, const void *base, size_t nums, size_t size, int (*compar)(const void *, const void *))

和 qsort 一樣是又臭又長，且隨我慢慢看，key 是指向要查詢的元素的指標，型別轉換為 void*，其他的和 qsort 裡的是一樣的不再贅述。

強調一下，bsearch（）的使用有一個硬性要求，這個陣列必須要有順序性，從大到小或從小到大否則達咩，所以建議和 qsort 配套實驗更佳。

這個 key 就是我們的查詢目標，void* 代表著一個指標，所以我們在函數裡面是不能直接給出的 key 的值，那我們就取他對應的地址就行

	int key = 5;
	bsearch(&key,arr,6,sizeof(int),compare1);

接下來順水推舟驗證一下：

 judge = (int*) bsearch (&key, values, 5, sizeof (int), cmpfunc);
   if( judge != NULL ) 
   {
      printf("find %d is truen", *judge);
   }
   else 
   {
      printf("%d can not be foundn", *judge);
   }
   
   return(0);
}

整個程式碼如下：

#include<stdlib.h>
int compare(const void* a, const void* b)
{
	int* p = (int*)a;
	int* q = (int*)b;
	int c = *p;
	int d = *q;
	return c - d;
}
int compare1(const void* key, const void* a)
{
	return (*(int*)key-*(int*)a);
}
int main()
{
	int* judge;
	int arr[6] = { 1,4,5,8,2,3 };
	qsort(arr, 6, sizeof(arr[0]), compare);
	int key = 5;
	judge = (int*)bsearch(&key, arr, 5, sizeof(int), compare1);
	if (judge != NULL)
	{
		printf("find %d is truen", *judge);
	}
	else
	{
		printf("%d can not be foundn", *judge);
	}

	return(0);
}

今天就先到這裡吧，摸了家人們，更多關於C語言庫函數qsort及bsearch快速排序演演算法的資料請關注it145.com其它相關文章！

C語言庫函數qsort及bsearch快速排序演演算法使用解析

目錄

qsort

含義

實現

格局開啟

bsearch

熱門文章