快捷導(dǎo)航

C語言?使用qsort函數(shù)來進(jìn)行快速排序

更新時間：2022年02月09日 15:05:25 作者：誠摯的喬治

排序方法有很多種：選擇排序，冒泡排序，歸并排序，快速排序等。?看名字都知道快速排序是目前公認(rèn)的一種比較好的排序算法。因?yàn)樗俣群芸?，所以系統(tǒng)也在庫里實(shí)現(xiàn)這個算法，便于我們的使用。?這就是qsort函數(shù)

前言

今天分享一個庫函數(shù)

介紹qsort的使用及實(shí)現(xiàn)方法

他可以實(shí)現(xiàn)不限于整形、浮點(diǎn)型、字符型、自定義等類型的排序

qsort的簡單介紹

	qsort
頭文件	＃include <stdlib.h>
格式	void qsort(void* base,size_t num,size_t width,int(__cdeclcompare(const void,const void*))
功能	實(shí)現(xiàn)多類型的快速排序
返回值	無返回值

把格式分解

void qsort(void* base, 
           size_t num, 
           size_t width, 
           int(* compare)(const void* e1, const void* e2)
           );

qsort的首參數(shù)為待排列數(shù)組的首地址

size_t num為某個類型的個數(shù)

size_t width為類型的寬度，也就是該類型的大小

int(* compare)(const void* e1, const void* e2)為比較函數(shù)的指針，這里是利用函數(shù)指針作為參數(shù)，實(shí)現(xiàn)傳參

這里運(yùn)用了回調(diào)函數(shù)的思想

回調(diào)函數(shù)就是通過函數(shù)指針調(diào)用的函數(shù)，如果把一個函數(shù)的指針（地址）當(dāng)作參數(shù)，傳給另一個函數(shù)，當(dāng)這個函數(shù)調(diào)用所指的函數(shù)時，我們就說這是回調(diào)函數(shù)。

用qsort實(shí)現(xiàn)一個整形類型的排序

#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1) - (*(int*)e2);
}
 
void test1()
{
	int arr[] = { 1,4,2,6,5,3,7,9,0,8 };
	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]);
	}
	printf("\n");
}
 
int main()
{
	test1();
	return 0;
}

用qsort函數(shù)實(shí)現(xiàn)結(jié)構(gòu)體的排序

#include<stdio.h>
#include<stdlib.h>
struct Stu
{
	char name[20];
	int age;
	float score;
};
 
int cmp_stu_by_socre(const void* e1, const void* e2)  //結(jié)構(gòu)體中的浮點(diǎn)型
{
	if (((struct Stu*)e1)->score > ((struct Stu*)e2)->score)
	{
		return 1;
	}
	else if (((struct Stu*)e1)->score < ((struct Stu*)e2)->score)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}
 
int cmp_stu_by_age(const void* e1, const void* e2)     //結(jié)構(gòu)體中的整形
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
 
int cmp_stu_by_name(const void* e1, const void* e2)    //結(jié)構(gòu)體中的字符型
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
 
void print_stu(struct Stu arr[], int sz)  //打印函數(shù)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d %f\n", arr[i].name, arr[i].age, arr[i].score);
	}
	printf("\n");
}
void test4()
{
	struct Stu arr[] = { {"zhangsan",20,87.5f},{"lisi",22,99.0f},{"wangwu", 10, 68.5f} };
	//按照成績來排序
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_socre);
	print_stu(arr, sz);
	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
	print_stu(arr, sz);
	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
	print_stu(arr, sz);
}
 
int main()
{
	test4();
	return 0;
}

結(jié)構(gòu)體的成員包括整形，浮點(diǎn)型和字符型

分別從小到大來排列

cmp函數(shù)通過返回值的正負(fù)性來實(shí)現(xiàn)比較大小，就可以實(shí)現(xiàn)下圖的結(jié)果

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

qsort函數(shù)在實(shí)現(xiàn)的時候，其實(shí)跟冒泡排序有一定的聯(lián)系

只不過

相對于冒泡排序，它可以排序各類型的數(shù)據(jù)，下面通過對比來實(shí)現(xiàn)其函數(shù)的功能

冒泡排序?qū)崿F(xiàn)整形的排序

void bubble(int arr[],int sz)  //冒泡排序?qū)崿F(xiàn)整形的排序
{
	int tmp = 0; int i = 0; int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j=0;j<sz-1;j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

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

void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
 
void bubble_sort(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 (arr[j] > arr[j + 1])
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//兩個元素的交換
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

可以看出有兩個地方有差異

首先就是兩個元素比較大小，是通過cmp比較函數(shù)實(shí)現(xiàn)

當(dāng)返回值大于零，函數(shù)就實(shí)現(xiàn)從小到大來排序

當(dāng)返回值小于零，函數(shù)就實(shí)現(xiàn)從大到小來排序

當(dāng)返回值等于零，元素不發(fā)生變化

第二個差異就是，實(shí)現(xiàn)兩個元素的交換

冒泡排序就是通過引入一個中間變量，達(dá)到交換的目的

而qsort函數(shù)，通過調(diào)用一個函數(shù)，通過引入寬度（所占字節(jié)的大?。?，進(jìn)行字節(jié)之間的交換，所以用char類型來實(shí)現(xiàn)不同類型的交換，所以首先需要知道排序數(shù)組內(nèi)每一個元素的大小，整形就交換四個字節(jié)的空間即可。

到此這篇關(guān)于C語言使用qsort函數(shù)來進(jìn)行快速排序的文章就介紹到這了,更多相關(guān)C語言 qsort函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: