模拟实现qsort函数

迷南。 2023-09-27 15:09 22阅读 0赞

**目录**

使用库函数来使用qsort

模拟实现qsort

整体代码展示

--------------------

我们在学习怎样模拟实现qsort函数之前，我们需要知道在库函数中qsort是怎么实现的。

## 使用库函数来使用qsort ##

先看看在库函数中qsort是怎样声名的：

void qsort(
    void* base,  //这里是我们要排序的目标数组
    size_t num,  //要排序的数组中元素的个数
    size_t width,  //每个元素的宽度，也就是每个元素所占的字节数
    int (*cmp)(const void* e1,const coid * e2))  //这个比较函数是需要我们使用者自己来实现的。

然后我们写一段代码来使用这个qsort库函数

#include<stdio.h>
    #include<stdlib.h>
    
    int cmp (const void* e1,const void *e2)
    {
    //以这种形式写，那么数组将会以升序的形式排序，如果你想以降序的形式排列就可以改成 
    return *(int*)e2-*(int*)e2
        return *(int*)e1-*(int*)e2;
    }
    
    int main()
    {
        int arr[] = {9,8,7,6,5,4,3,2,1,0,};
        int len = sizeof(arr)/sizeof(arr[0]);
        qsort(arr,len,sizeof(arr[0]),cmp);
        for(int i = 0; i<10; i++)  //将数组打印出来观察
        {
            printf("%d ",arr[i]);
        }
    
        return 0;
    }

## 模拟实现qsort ##

知道了怎样直接使用库函数qsort之后，我们就可以仿照库函数来自己模拟实现。代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    void swap(char* e1,char* e2,size_t width)
    {
        for(int i = 0; i<width; i++)
        {
            char tmp = *e1;
            *e1 = *e2;
            *e2 = tmp;
            e1++;
            e2++;
        }
    }
    
    int cmp(const void* e1,const void* e2)
    {
        return *(int*)e1-*(int*)e2;  //这里强制转换类型需要根据你的数组内容来改变
    }
    
    void my_qsort(void* base,size_t len,size_t width,int (*cmp)(const void* e1,const void *e2))
    {
        for(int i = 0; i<len; i++)
        {
            for(int j = 0; j<len-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) ,size_t width);
                }
            }
        }
    }
    
    int main()
    {
        int arr[] = {9,8,7,6,5,4,3,2,1,0};
        int len = sizeof(arr)/sizeof(arr[0]);
        my_qsort(arr,len,sizeof(arr[0]),cmp);
    
    return 0;
    }

这里我们还可以使代码更加优化，那就是定义一个flag变量，将他赋值为一，如果有交换就将flag改为0，如果循环结束后flag还为1，那么就说明该躺排序没有元素进行交换，都没有进行交换的话，就说明此时数组中的元素已经达到了我们的目的，我们就可以直接结束函数，大大的提高了代码的运行效率。

## 整体代码展示 ##

#include<stdio.h>
    #include<stdlib.h>
    
    void swap(char* e1,char* e2,size_t width)
    {
        for(int i = 0; i<width; i++)
        {
            char tmp = *e1;
            *e1 = *e2;
            *e2 = tmp;
            e1++;
            e2++;
        }
    }
    
    int cmp(const void* e1,const void* e2)
    {
        return *(int*)e1-*(int*)e2;  //这里强制转换类型需要根据你的数组内容来改变
    }
    
    void my_qsort(void* base,size_t len,size_t width,int (*cmp)(const void* e1,const void *e2))
    {
        for(int i = 0; i<len; i++)
        {
            int flag = 1;
            for(int j = 0; j<len-1-i; j++)
            {
    //我这里还是以升序为例，如果前面一个元素大于后面一个元素就交换，
    如果你想以降序排列的话就将>换成<
                if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)
                {
                    flag = 0;
                    swap((char*)base+j*width,(char*)base+(j+1)*width) ,size_t width);
                }
            }
            if(1 == flag)
            return;
        }
    }
    
    int main()
    {
        int arr[] = {9,8,7,6,5,4,3,2,1,0};
        int len = sizeof(arr)/sizeof(arr[0]);
        my_qsort(arr,len,sizeof(arr[0]),cmp);
    
    return 0;
    }

这就是模拟实现qsort函数的全部内容了，感谢大家的观看。