qsort函数详解以及模拟实现

灰太狼 2024-03-30 15:08 75阅读 0赞

#### qsort函数详解以及模拟实现 ####

*  一.qsort函数是什么
 *  二.具体的使用
 *   *  1.参数4（参数3在模拟实现时解释）
     *  2.例子
     *   *  1.排序整形
         *  2.排序结构体
 *  三.模拟实现qsort
 *   *  1.参数3
     *  2.模拟排序
     *   *  1.排整形
         *  2.排结构体

![在这里插入图片描述][486b81afa3bc4c73b13779b7379f31b8.png]

## 一.qsort函数是什么 ##

*这里会使用到函数指针，如果还不太了解的话可以看看这篇博客[指针进阶][Link 1]*

> **qsort全称为quick\_sort（快速排序），为什么这么称呼呢？因为它实现的内核就是依靠快排来实现的。但与单纯的快排不同的是，它是库函数并且可以排序任意类型的数据（整数，字符，结构体，字符串…）。**

*接下来再MSDN里详细看看它的全貌*

![在这里插入图片描述][f565c1bfd02c46cfaa81dc1dd295e318.png]

> **可以看到它的头文件是stdlib.h，并且参数很多接下来会详细解析。**

![在这里插入图片描述][9e89070ef49e41dba3065b26e207c88c.png]

![在这里插入图片描述][95197dc6839c4befa3fe0b01c101525c.png]

*base*

> **第一个参数是base，在MSDN里的解释是Start of target array。也就是目标数组的开始。**

**第一个参数传目标数组的起始位置。**

*num*

> **第二个参数是num，在MSDN里的解释是Array size in elements。也就是数组的大小。**

**第二个参数传数组的大小。**

> **第三个参数是width，在MSDN里的解释是Element size in bytes。也就是每个成员的大小。**

**第三个参数是每个元素占的字节大小。**

> **第四个参数是一个函数指针指向compare。在MSDN里的解释是Comparison function。也就是比较功能。**

**第四个参数传一个函数指针，它所指向的函数要具备比较功能。**

## 二.具体的使用 ##

### 1.参数4（参数3在模拟实现时解释） ###

> **关于函数的参数，参数1，2自然不必多说（要排序自然得知道起始位置和数组大小）。对于参数4，如果我们只需要比较整形，我们自然可以只是向上面的冒泡排序一样直接使用大于比较，但如果是一个字符串呢？如果是一个结构体呢？那么我们当然不能简单的用大于小于这些符号来比较，我们需要自己写一个判断规则，这就是参数4的意义。明确判断规则。也是qsort能排序任意类型数据的关键。**

*详细说明参数4需要的参数*

![在这里插入图片描述][336315748e5d40f29de6c745abfbecb2.png]

**1.e1是你需要比较元素的第一个元素的地址，e2是另一个元素的地址。  
2.两个参数的类型都是const void \*  
3.const是为了防止参数在函数内部被改变  
4.void\*是无具体类型的指针（下面重点说明一下）**

![在这里插入图片描述][29be397ba1e74901a581d90bfd4ce7ea.png]

> **但对于这个函数来说肯定是需要接收不同类型的指针的，各。void\*是通用指针。好处是可以接收各种指针，坏处是不能直接解引用，因为连它自己都不知道自己是什么类型。**

![在这里插入图片描述][4bb168476ea34622b21a954444a0c0b0.png]  
![在这里插入图片描述][5a76a67047e246128ac88fa0423b7e9d.png]

### 2.例子 ###

#### 1.排序整形 ####

> **上面说到void\*不能直接解引用，所以需要我们进行强制转换。这样才能够使用。ps:由于参数4是函数指针，所以我们应该传函数地址，函数名就表示函数地址。**

![在这里插入图片描述][a5a09c5d8a2149e19c42db9f6e57b4c3.png]

> **这个函数总得有返回值吧，来看看MSDN。**

![在这里插入图片描述][4e8b596fa62b4dfb83b286c558133087.png]

> **如果第一个元素小于第二个元素，返回一个小于0的数。如果相等则返回0；如果大于，则返回大于0的数。那么我们就按照它的要求书写。**

![在这里插入图片描述][bb5ec41a713b4fd9a5973916d2fb4246.png]

> **来看看结果。**

![在这里插入图片描述][01dd550e9040475b958f22b868ee54db.png]

> **当然以上是升序，如果想要降序的话直接调个方向就可以了。**

![在这里插入图片描述][1ce20ec3d4b846cd9e5cf9b1e6131e49.png]

#### 2.排序结构体 ####

![在这里插入图片描述][9b5cf2096979426a99d1f91d35fcf9ce.png]

*首先按照年龄排成升序*

![在这里插入图片描述][fb54a52302004c5caf50f057d58e21c0.png]

![在这里插入图片描述][0c5877947fc9417cb7e33b4508ffda2b.png]

**可以看到确实按照年龄的升序来排列的。**

*按照名字来排列*

> **名字是字符串不能直接使用减号，需要用到strcmp。它是按照对应位置字符大小来比较的。**

![在这里插入图片描述][2057b889b91f46d5807ee70ac0c2ccaf.png]

> **我们知道该函数需要返回数字，而恰好strcmp满足这个要求。所以我们只需要直接返回strcmp就可以了（注意头文件是string.h）。**

![在这里插入图片描述][c7a0253016ee4e828744f392c7d49c7e.png]

![在这里插入图片描述][668076fc9d80407f84287daf7d9dd4c2.png]  
![在这里插入图片描述][30860bf2d66f4c96b69009f92e013a3d.png]

> **由于l<w<z，所以排序应该是lisi,wangwu,zhangsan，也可以看到确实是这样排序的。**

**总结：需要排列什么数据取决于参数4所指向的函数如何判断。**

## 三.模拟实现qsort ##

> **上文提到qsort是依托快排实现的，但由于快排有些复杂，这里就使用冒泡排序作为内核。（如果还有些不明白的可以看看这篇博客 [冒泡排序][Link 2]）**

![在这里插入图片描述][5f676cfa8dba4d6f81e1ea876c5380e6.png]

> **这是一个简易的冒泡排序，它也能够排列数据。但与qsort不同的是，它只能排列整数。所以接下来我要改造它，使它能够排列任意数据。（ps：这里目前不考虑时间，空间，稳定性之类的）。**

**上文说过，qsort能排列任意数据，关键在于你写的判断函数，也就是参数4。所以我们也应当对冒泡排序的判断条件进行修改。将它封装为一个函数。**

![在这里插入图片描述][ac5ba7de69e84d93b21abe3f29e3f9c0.png]

> **既然我们要模拟qsort，那么参数也应当于qsort保持一致。ps:为什么要传这些参数，开头已经说过，但参数3还未说过，接下来讲解为什么要传每个元素的宽度。**

### 1.参数3 ###

**1.首先我们第一个参数是void \* ，也就是我们根本不知道到底传递的是什么类型，我们需要参数3来确定是哪种类型。  
2.方便我们找到每个元素（具体使用请看模拟过程）**

### 2.模拟排序 ###

![在这里插入图片描述][b228dac74f2243778791637e77c2b261.png]

> **再次说明参数4是函数指针，它所指向的函数就是我们所写的判断规则，再根据cmp的返回值，如果大于0我们就交换两个数据。接下来的关键是我们如何给cmp传参，也就是我们如何精确的找到这两个元素，然后进行判断。**

> **冒泡排序的内核是相邻两个元素两两进行比较，所以我们com里也应该两两相邻元素进行比较。由于我们根本不知道数据类型，不能使用下标来算，需要用地址来间接寻找，这也体现出了参数3的作用。**

![在这里插入图片描述][de07dd93aad343429e60e41c91414ff7.png]

![在这里插入图片描述][b495df8d9c914dc5b419dc22c0141da6.png]

> **接下来是如何交换，由于类型不明，我们肯定不能直接交换。但是无论什么元素它的单位都是字节，那么我们可以一个字节一个字节的交换，写一个交换函数挨个交换它们的字节。**

![在这里插入图片描述][f7866d2fd048455bab46e75aab974e30.png]

![在这里插入图片描述][655b5b9b636e4f94a873e1396970fd75.png]

![在这里插入图片描述][127d088263574a8ba14aca86b740feac.png]

**以上就是模拟实现的qsort，任意数据都可以排序，接下来来验证一下。**

#### 1.排整形 ####

![在这里插入图片描述][8d2c53834b844492a920bde50011ea80.png]

#### 2.排结构体 ####

*按年龄*

![在这里插入图片描述][5cb5c37b2907425aa01e2de7ea8ffae1.png]

*按名字*

![在这里插入图片描述][1f56b0894d334aacb784f5826721bd8c.png]

**总结：由于qsort需要适合各种类型，所以我们传参除了部分明确的外都是void。qsort如何精确的找到两个数依赖于数据的地址。不同类型数据的比较方法是不同的，所以需要我们自己写判断规则。**

*以下是判断结构体学生名字的全部代码*

void Swap(char* buf1, char* buf2, int width)//由于我们已经强转为char*了，这里就已经明确类型了
    {
        
    	for (int i = 0; i < width; i++)
    	{
        
    		char tmp = *buf1;
    		*buf1 = *buf2;
    		*buf2 = tmp;
    		buf1++;
    		buf2++;
    	}
    }
    
    
    void bubble_sort(void*base,size_t sz,size_t width,int(*cmp)(const void*e1,const void*e2))
    {
        
    	size_t i = 0;
    	size_t j = 0;
    	size_t tmp = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
                                                
    		for (j = 0; j < sz - 1 - i; j++)
    		{
        
    			if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)
    			{
                                                              
    				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);//要交换字节，除了两个元素外肯定还得知道它们的大小
    			}
    		}
    	}
    }
    
    struct stu
    {
        
    	char name[20];
    	int age;
    };
    int cmp_stu_name(const void* e1, const void* e2)
    {
        
    	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
    }
    
    int main()
    {
        
    	struct stu s[3] = {
         {
        "zhangsan",20},{
        "lisi",40},{
        "wangwu",33} };
    	bubble_sort(s, 3, sizeof(s[0]), cmp_stu_name);
    
    	return 0;
    }

![在这里插入图片描述][022a9a9475b24fc5a0e23b5fce765d66.png]

[486b81afa3bc4c73b13779b7379f31b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3aed480d8d144ac5810b6ad2147daaac.png
[Link 1]: http://t.csdn.cn/IYReb
[f565c1bfd02c46cfaa81dc1dd295e318.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5ff4a9f5e5cd4ac9a0edc5605e0748e7.png
[9e89070ef49e41dba3065b26e207c88c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5f330f4c7639465a98229470c20dd7ef.png
[95197dc6839c4befa3fe0b01c101525c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0c235371c0274bf29febd4221d04170d.png
[336315748e5d40f29de6c745abfbecb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/52e3885a885441449ec59243534b8955.png
[29be397ba1e74901a581d90bfd4ce7ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7081bcfca90b480d84b85c9ab184bc8f.png
[4bb168476ea34622b21a954444a0c0b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/efa7d57c185e412f8c2e409b91139f0e.png
[5a76a67047e246128ac88fa0423b7e9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6a05b1eff96d43e2b8fe57bb9815a771.png
[a5a09c5d8a2149e19c42db9f6e57b4c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/398f79883f1944168e522b5c2de74b34.png
[4e8b596fa62b4dfb83b286c558133087.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6698551a4ff142cebb9e64c809fe5be6.png
[bb5ec41a713b4fd9a5973916d2fb4246.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6e215d91715847d0929ae91127a6d2c3.png
[01dd550e9040475b958f22b868ee54db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/114a2da861f142f79536c019d09d6e30.png
[1ce20ec3d4b846cd9e5cf9b1e6131e49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/339c5c245d6a40faabb13574c577beb4.png
[9b5cf2096979426a99d1f91d35fcf9ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f575d7eea48e48cebd6167bbb7606b40.png
[fb54a52302004c5caf50f057d58e21c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8040687be91748a798866fd9041ea121.png
[0c5877947fc9417cb7e33b4508ffda2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a8d98e185482424f991e188d2eea1407.png
[2057b889b91f46d5807ee70ac0c2ccaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/54037b1d17dc462081e8da7cdd687baf.png
[c7a0253016ee4e828744f392c7d49c7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8c4012519216404184fd3f78cf91e684.png
[668076fc9d80407f84287daf7d9dd4c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/046a0733ef134f40800d728d8f2a641e.png
[30860bf2d66f4c96b69009f92e013a3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/558a6ac033404d64b661d2896e1b1410.png
[Link 2]: http://t.csdn.cn/4kw4P
[5f676cfa8dba4d6f81e1ea876c5380e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f6a5350e040449718fb0d0740f0f15fc.png
[ac5ba7de69e84d93b21abe3f29e3f9c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/21563437b2fc434b9a79a246047f6642.png
[b228dac74f2243778791637e77c2b261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/52515533dd1547508c912c5736f02f23.png
[de07dd93aad343429e60e41c91414ff7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/83768e8b6bce4bf5ae531b9a116f465e.png
[b495df8d9c914dc5b419dc22c0141da6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2179af407cb642c4819c6f2d3e03fa9d.png
[f7866d2fd048455bab46e75aab974e30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2637f532d53742b6b550179b6189a42f.png
[655b5b9b636e4f94a873e1396970fd75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/90427d08de2b4d36ad6d8d55740be1aa.png
[127d088263574a8ba14aca86b740feac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b98eff75b4584604bac404cb90d17614.png
[8d2c53834b844492a920bde50011ea80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8b2cf2f5d8704e6ea35c42bd5238e9c1.png
[5cb5c37b2907425aa01e2de7ea8ffae1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5fe32de695774241a17892b0f2f7a41e.png
[1f56b0894d334aacb784f5826721bd8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ec5b745742434adea336798a27ddf866.png
[022a9a9475b24fc5a0e23b5fce765d66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2017c6cc7285437f86ae60d45e189f69.png