用冒泡排序法实现qsort函数

谁借莪１个温暖的怀抱￠ 2022-08-21 12:44 198阅读 0赞

—、qsor函数：

qsort函数是一个能排序任何数据类型的函数，让我们先来了解一下qsort函数的形参和返回值。

void qsort( void \**base*, size\_t *num*, size\_t *width*, int (\_\_cdecl\**compare*(const void \**elem1*, const void \**elem2* ) );

函数原型中qsort函数有四个参数，分别为：

base:是指目标数组的开始位置，可以理解为数组首元素的地址；

num:是指数组中元素的个数；

width:是指数组中每个元素的类型的大小；

compare:是一个函数指针，是一个比较函数，它的返回值是int,通过它来判断要比较的元素的类型；

compare函数需要程序员自己来写以辅助qsort函数对不用类型的数组进行排序

二、qsort函数的模拟实现

qsort可以实现多种类型的排序，我们可以模拟实现它。

要实现它我们要注意以下几点：

要实现这个函数我们首先要有比较函数，用来比较两个元素大小，判断返回值的大小来确定是否要交换两个元素。 比较函数应设计为返回值int,参数为void \* 类型的指针 ，因为我们要实现多种类型的元素的排序。

还要一个交换函数，当两元素满足交换条件是交换它们。 交换函数的类型应该为返回值为void，参数为两个char \*类型指针（元素类型不同） ，还有一个是元素类型的大小（字节）。交换时应该以字节为单位交换。

#include <stdio.h>
         #include <string.h>
         void swap(char* arr1, char* arr2, int sz)
    {
    	int i = 0;
    	char tmp;
    	for (i = 0; i < sz; i++)
    	{
    		tmp = *(arr1 + i);
    		*(arr1 + i) = *(arr2 + i);
    		*(arr2 + i) = tmp;
    	}
    }
    //int compare_int(const void *elem1, const void *elem2)
    //{
    //	return (*(int*)elem1 - *(int*)elem2);
    //}
    int compare_str(const void *elem1, const void *elem2)
    {
    	return strcmp((char *)*(int *)elem1, (char *)*(int *)elem2);
    }
    void my_qsort(const void *base, size_t num, size_t width, int( *compare)(const void *elem1, const void *elem2))
    {
    	int i, j;
    	char* arr =(char *) base;
    	for (i = 0; i < num - 1; i++)
    	{
    		//int flag = 0;
    		for (j = 0; j < num - i - 1; j++)
    		{
    			if (compare_str((char *)(arr + width*j), (char *)(arr + (j + 1)*width))>0)
    			{
    				//flag = 1;
    				swap((char *)(arr + j*width), (char *)(arr + (j + 1)*width), width);
    			}
    
    		}
    	}
    }
    
    
    int main()
    {
    	int i;
    	char* arr[] = { "bbbbbb", "cccccc", "aaaaaaa" };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	my_qsort(arr, sz, sizeof(char *), compare_str);
    	for (i = 0; i < sz; i++)
    	{
    		printf("%s  ", arr[i]);
    	}
    	return 0;
    }