qsort的使用与实现

c语言常见的排序方法大概有这些，今天我们所讲的是就是qsort快排的讲解

头文件

qsort的使用

我们先使用msdn查看他的相关资料，得知这个函数的传参请情况

1.void *base

翻译过来就是将要排序的函数的起始位置/数组首元素地址

2.size_t num

翻译过来就是数组个数(要注意这里的个数是指该数组元素的个数，单位是个)

3.size_t width

翻译过来就是每个元素大小(以字节计)

4. int (__cdecl *compare )(const void *elem1, const void *elem2 )

最后一个参数看起来很长，但实际看起来，他就是一个函数指针，我们看看在msdn上他的解释是什么

compare elem1 elem2

[数] 比较函数指向搜索键的指针指向要与键进行比较的数组元素的指针

经过阅读以上文章得知，compare函数的作用便是

compare( (void *) elem1, (void *) elem2 );

所以我们便不难实现compare函数

返回类型为int 两个形参全都是void*

int compare(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

以上就是通过msdn查阅资料得知其功能，从而得知其的使用方法

以下排序展示效果

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

代码运行起来便是如此效果

当然降序只需要将第四个参数的逻辑该反，具体就是如下

int compare(const void* e1, const void* e2)
{
	return (*(int*)e2 - *(int*)e1);
}

qsort排序结构体

上文的使用只在整形数组内使用了，但如果是结构体的话使用会不会又不同呢？

我们带着这个疑问，对上文的代码进行改进，使其可以对结构体排序；

#include <stdio.h>
#include<stdlib.h>
struct stu
{
	char name[20];
	int age;
	char sex[5];
};
int compare(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
int main()
{
	struct stu s[3] = { {"李四",20,"男"},{"王五",20,"男"} ,{"赵四",20,"男"} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]),compare);
	int i = 0; 
	for (i = 0; i < sz; i++)
	{
		printf("%s %d %s\n", s[i].name, s[i].age, s[i].sex);
	}
	return 0;
}

貌似也是可以行的通的，但是思考过后,发现我们是以什么方式排序的呢？我们没有修改第四个形参的函数的内部修改，第四个形参的作用就意在说明我们是利用什么方式在排序，（结构体以名字排序）那么我们就对于不同的类型要使用不同的compare，

以下代码便是compare 通过name

#include<string.h>
int com_name(const void* e1, const void* e2)
{
	return (strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name));
}//这里一定要记得强制类型转换

qsort的实现（排序整形）

qsort我们会用以后，那么就要去尝试着怎么自己实现，

我们先看以下冒泡排序的实现方法

void Bubble_sort(int arr[], int size)//int arr[]等价于int *arr
{
	int j, i;
	for (i = 0; i < size - 1; i++)//size-1是因为不用与自己比较，所以比的数就少一个
	{
		int count = 0;
		for (j = 0; j < size - 1 - i; j++)	//size-1-i是因为每一趟就会少一个数比较
		{
			if (arr[j] > arr[j + 1])//这是升序排法，前一个数和后一个数比较，如果前数大则与后一个数换位置
			{
				int tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
				count = 1;

			}
		}
		if (count == 0)			//如果某一趟没有交换位置，则说明已经排好序，直接退出循环
			break;
	}
}
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int i = 0;
	Bubble_sort(arr, 10);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

所标红的地方便是相当于qsort里面第四个参数（比较），我们在冒泡排序实现代码基础上进行修改

对于实现者：不知道排序的是什么类型的数组

对于使用者：知道其排序的是什么类型的数组

所以使用去qsort最重要的是对于不同类型使用的com（第四个参数）是不同的

对于第一个参数

msdn上是void*类型的，void*类型的好处就是可以接受任何类型的地址，利用这一点就可以排序任何类型的数组

对于第二个参数跟冒泡排序的参数sz一样，第三个参数与第一个参数结合，不就是解释了每个元素大小（把第一个参数强制类型转化为char*）（也大致就了解是什么类型）达到了冒泡排序第一个参数作用

修改参数：

void Bubble_sort(void* base, 
	size_t num, 
	size_t width, 
	int (*com)(const void* e1, const void* e2)
)

大致思路路就是

com（比较大小）

if (com((char*)base + j * width, (char*)base + (j + 1) * width)>0)

int com(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

swap（交换）

swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

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++;
	}
}

总结

#include<stdio.h>
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++;
	}
}
int com(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void Bubble_sort(void* base,size_t num,size_t width,int (*com)(const void* e1, const void* e2))
{
	int j, i;
	for (i = 0; i < num - 1; i++)
	{
		int count = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if (com((char*)base + j * width, (char*)base + (j + 1) * width)>0)
			{
					swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}	
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr, sz, sizeof(arr[0]), com);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}