目录

1. 快速排序

1.1 快速排序理论分析 

1.2 快速排序的模拟实现 

2. qsort的模拟实现 

2.1 qsort的理论分析

2.2 qsort的模拟实现

---

qsort函数是基于快速排序思想设计的可以针对任意数据类型的c语言函数。要对qsort进行模拟实现，首先就要理解快速排序。

1. 快速排序

1.1 快速排序理论分析 

上一期博客选择排序，冒泡排序，插入排序，快速排序及其优化-****博客我们大概讲解了快速排序的思路，现在我们来详细讲解以下快速排序。

 让我们来逐帧分析快速排序的思想。

1. 第一步便是找到基准数，开始分区：基准数可以选择第一个，最后一个，也可以是随机的（为了便于理解，以下的图都默认选的是第一个，当然代码是随机的，重要的是先把交换三个数的本质理解到）

2.  分而治之，调整后基准数的左右两边，再进行相同的操作，直到不能再排序（数组长度为1时，就不能再排序了）

 

1.2 快速排序的模拟实现 

以上便是对快速排序底层逻辑的分析， 接下来以c语言为例，讲解模拟实现快速排序。

1. 选一个基准数，这里选的是首元素

2. 开始分区，遍历整个数组，开始交换位置（三个数），小的在前，大的在后

3. 开始递归，左右两边都要开始递归，由于需要知道边界，所以分区时，应该再返回基准数的地址。同时为了避免递归递而不归，应设置最小的长度

/*
	返回值：基准数最后的下标
	参数：需要分区的部分（从头到尾开始排）
*/
int partition(int arr[], int start, int end)
{
	int len = end - start;
	int* ppivot = arr + start;
	int* s = ppivot + 1;
	while (len--)
	{
		if (*ppivot >= *s)
		{
			int temp = *s;
			*s = *(ppivot + 1);
			*(ppivot + 1) = *ppivot;
			*ppivot = temp;
			ppivot++;
		}
		s++;
	}
	return ppivot - arr;
}


/*
	返回值：arr首元素的地址
	参数：需要排序的部分（从头到尾）
*/

int* quick_sort(int arr[], int start, int end)
{
	assert(arr);
	int* p = arr;
	if (end > start)
	{
		int pivot = partition(arr, start, end);
		quick_sort(arr, start, pivot - 1);
		quick_sort(arr, pivot + 1, end);
	}

	return p;
}

 当然，对于分区的排序可以进行优化，使用双指针也可以。双指针就是首尾往中间交换的模式，效率自然更高。这里不过多展开去讲。

2. qsort的模拟实现 

2.1 qsort的理论分析

C 库函数 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 对数组进行排序。它可以接收任意类型进行排序，其实跟快速排序接收int类型差不多，只是这里多了一个强制类型转换。

2.2 qsort的模拟实现

qsort的模拟实现，基本就是在quick_sort上做改造，将原来只可以进行int数据类型的改成任意数据类型。

1. 原来是数值之间的比较，现在要改成有专门的比较数据大小的函数（字符：strcmp）

2. 交换位置，原来int直接就可以交换数据，现在强制类型转换成char*后，单位转换的变少了，则需要循环4次，才够int 四个字节

3. 指针加1， 原来有确定类型，现在是void* 原来加1，现在就应该加size

int cmp_int(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}

/*
	返回值：基准数最后的下标
	参数：需要分区的部分（从头到尾开始排）
*/
int partition(void* arr, int start, int end, size_t size)
{
	int len = end - start;
	char* ppivot = ((char*)arr + start * size);
	char* s = ppivot + size;
	while (len--)
	{
		if ((*cmp_int)(ppivot, s) > 0)
		{
			for (int i = 0; i < size; i++)
			{
				int temp = *(s+i);
				*(s+i) = *(ppivot + size + i);
				*(ppivot + size + i) = *(ppivot+i);
				*(ppivot+i) = temp;
			}

			ppivot += size;
		}
		s += size;
	}
	return (int)((ppivot - (char*)arr) / size);
}


/*
	返回值：arr首元素的地址
	参数：需要排序的部分（从头到尾）
*/

void* quick_sort(void* arr, int start, int end,size_t size)
{
	assert(arr);
	if (end > start)
	{
		int pivot = partition(arr, start, end,size);
		quick_sort(arr, start, pivot - 1,size);
		quick_sort(arr, pivot + 1, end,size);
	}

	return arr;
}


void* my_qsort(void* arr, size_t len, size_t size, int (*cmp_int)(const void* a, const void* b))
{
	assert(arr);
	int start = 0;
	int end = (int)len - 1;
	quick_sort(arr, start, end, size);
	return arr;
}

感谢各位大佬的支持与指正！！！