• C语言之qsort()函数的模拟实现

    C语言之qsort()函数的模拟实现

    文章目录

    1. 简介

    qsort()函数全称为Quicksort，因为底层使用的是快速排序，对初学者来说只学过冒泡排序，使用我们使用冒泡排序来实现下qsort()函数，qsort()函数（冒泡排序版）

    不知道qsort函数怎么使用的可以看看这篇qsort函数

    2. 冒泡排序

    既然要使用冒泡排序改模拟实现qsort，那得知道什么是冒泡排序
    代码如下：

    #include 

void bubble_sort(int arr[], int sz)
{
	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])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
    int arr[] = { 1,4,7,2,5,8,3,10,6,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    3. 对冒泡排序进行改造

    void bubble_sort(int arr[], int sz);
void qsort (void* base, 
            size_t num, 
            size_t size,            
            int (*compar)(const void*,const void*));

    • 1
    • 2
    • 3
    • 4
    • 5

    先来看看冒泡排序和qsort函数的函数声明
    要想用冒泡排序模拟实现qsort函数，首先函数的形参要一致

    void bubble_sort2(void* base,
                  size_t sz,
                  size_t width,  
                  int (*cmp)(const void* p1,const void* p2));

    • 1
    • 2
    • 3
    • 4

    仿照着qsort的形参来写

    1. void*：由于我们不知道要排序什么数组，所以我们使用void*来接收
    2. sz：为数组中元素的个数
    3. width：为数组中一个元素的大小（单位为字节）
    4. int (cmp)(const void p1,const void* p2)：是函数指针
      这个函数指针指向的函数是用来比较两个元素的大小
      p1指向一个元素，p2也指向一个元素

    函数的声明部分写好了，就得改造函数内部了
    先来看看冒泡排序中的代码
    在这里插入图片描述

    1. 首先函数的形参得更改吧 改为上边的函数声明
    2. 趟数取决于数组中元素个数使用不需要修改
    3. 冒泡排序只能排序整型，所以一趟冒泡排序中的比较部分需要修改
    4. 交换两个元素的位置也需要修改

    4. 改造部分

    4.1 保留部分的冒泡排序

    先将冒泡排序还能使用的部分保留下来

    void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		//一趟冒泡排序
		for (j = 0; j < sz - 1 - i; j++)
		{
			//比较两个元素的大小
			if ()
			{
				//Swap用于交换两个元素的位置
				Swap();
			}
		}
	}
}

int main()
{
	int arr[] = { 1,4,7,2,5,8,3,10,6,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    其中的比较部分和交换部分需要我们自己来实现

    4.2 比较部分

    cmp((char*)base + j * width, (char*)base + (j + 1) * width)

    • 1

    1. 由于我们得到的数组名，也就是首元素的地址，不知道第二个元素的地址
      我们可以通过指针偏移来找到第二个元素

    2. 我们得到的是void类型的数据，我们需要将其强制转换成char类型的数据，以便于我们进行指针偏移

    3. 不知道数组的类型，我们只知道一个元素的大小，我们可以通过(char*)base + j + width的方式来找到一个元素的地址，(char*)base + (j+1) + width的方式来找到后一个元素的地址
      用来模拟arr[j] 和 arr[j+1]
      在这里插入图片描述

    4. 为什么其他类型的指针不行呢，我来举个例子：

    假设用来排序double类型的数据，也就是每个元素是8字节 width = 8
    (char*)base + j * width 和 (char*)base + (j+1) * width
    当j等于0时，char类型的指针会偏移8个字节，找到第二个元素
    如果换成其他类型的指针 int* 在这个情况下就不能使用了，只有char*类型的指针偏移是1个字节，适用于任意类型的排序

    4.3 交换部分

    void Swap(char* p1, char* p2,size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1. 由于在比较部分已经将数据强制转换成char类型，所以Swap函数的形参就可以使用char来接收
    2. 由于不知道接收的是什么类型的数据，但是我们知道每个元素的大小，我们可以通过一个字节一个字节进行交换，和冒泡排序一样定义一个临时变量来交换两个元素，交换完一个字节的内容之后，p1++ p2++来找到第二个字节的内容，直到交换完成

    5. bubble_sort2完整代码

    void Swap(char* p1, char* p2,size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		//一趟冒泡排序
		for (j = 0; j < sz - 1 - i; j++)
		{
			//比较两个元素的大小
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//Swap用于交换两个元素的位置
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    6. 使用bubble_sort2来排序整型数组

    和使用qsort函数一样，第四个形象需要根据需要排序的数据类型来编写函数，然后将其传给qsort函数，整型数据的比较只需要两个元素作差就好了
    代码如下：

    int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}

    • 1
    • 2
    • 3
    • 4

    排序整型数组的完整代码：

    #include 

void Swap(char* p1, char* p2,size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		//一趟冒泡排序
		for (j = 0; j < sz - 1 - i; j++)
		{
			//比较两个元素的大小
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//Swap用于交换两个元素的位置
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}

int main()
{
	int arr[] = { 1,4,7,2,5,8,3,10,6,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    代码运行结果如下：
    在这里插入图片描述

    7. 使用bubble_sort2来排序结构体数组

    由于结构体中的数据类型较多，可以选择一种来排序，然后根据不同的数据类型来排序
    按以下两种数据来举例子

    struct Stu 
{
	char name[20];
	int age;
};

```c
int main()
{
	struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d\n", arr[i].name, arr[i].age);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    7.1 按名字来排序结构体数组

    字符串的比较是比较ASCII，不是比较字符串的长度

    int cmp_struct_by_name(const void* p1, const void* p2)
{
	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
	//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);
	//两段代码等价
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    完整代码如下：

    #include 
#include 

void Swap(char* p1, char* p2,size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		//一趟冒泡排序
		for (j = 0; j < sz - 1 - i; j++)
		{
			//比较两个元素的大小
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//Swap用于交换两个元素的位置
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

struct Stu 
{
	char name[20];
	int age;
};

int cmp_struct_by_name(const void* p1, const void* p2)
{
	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
	//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);
	//两段代码等价
}

int main()
{
	struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d\n", arr[i].name, arr[i].age);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    代码运行结果如下：
    在这里插入图片描述

    7.2 按年龄来排序结构体数组

    int cmp_struct_by_age(const void* p1, const void* p2)
{
	return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
	//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
	//两段代码等价
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    完整代码如下：

    #include 
void Swap(char* p1, char* p2,size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		p1++;
		p2++;
	}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		//一趟冒泡排序
		for (j = 0; j < sz - 1 - i; j++)
		{
			//比较两个元素的大小
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//Swap用于交换两个元素的位置
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}



struct Stu 
{
	char name[20];
	int age;
};

int cmp_struct_by_age(const void* p1, const void* p2)
{
	return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
	//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
	//两段代码等价
}
int main()
{
	struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_age);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d\n", arr[i].name, arr[i].age);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    代码运行结果如下：
    在这里插入图片描述

  • 相关阅读:
    Python---多线程
    HR人才测评，采用线上测评做春招秋招
    【Go 基础篇】Windows 开发常用 Dos 命令
    Pytorch实战 | 第P1周：实现mnist手写数字识别
    【STL】函数对象（仿函数）谓词 内建函数对象
    价值1000的情感爆文写作prompt，助你写出10万+阅读微信爆文
    1758. 生成交替二进制字符串的最少操作数
    C# Winform中在DataGridView中添加Button按钮,操作Button按钮
    【Linux】Linux小程序(进度条)、git命令行的使用及gdb的使用
    『无为则无心』Python面向对象 — 54、重写和super()函数
  • 原文地址：https://blog.csdn.net/qq_47386786/article/details/134496670