qsort使用和模拟

我们先来了解一下qsort的如何使用，qsort也是一种排序，是快速排序quick  sort

使用qsort时要包含#include<stdlib.h>

qsort的参数非常多，让我们来一 一了解：

void qsort (
             void* base,//第一个参数，base指向的是待排序数组中首元素的地址
             size_t num,//第二个参数，num指向的是待排序数组中元素个数
             size_t size,//第三个参数，size指向的是待排序数组中每个元素的大小，单位字节
             int (*compar)(const void*,const void*)
            //第四个参数，是一个函数指针，用来比较base指向的数组中任意的俩个元素的大小
            );

这里我们思考一下为什么第一个参数是void*呢？

因为qsort并不知道未来的你会用qsort来排序什么类型，所以用泛型指针void*来接收，后面我们自己强制类型转换即可

接下来让我们实操一下qsort来排序整型数组：

#include<stdio.h>
#include<stdlib.h>
int cmp_arr (const void*e1,const void*e2)
{
   return *(int*)e1 - *(int*)e2;
//这里因为我们创建的数组是int类型，所以要强制类型转换int*类型
}

void print_arr(int arr[],int sz)
{
  int i=0;
  for(i=0;i<sz;i++)
  {
    printf("%d ",arr[i]);
  }
   printf("\n");//打印完后换行
}

int main()
{
  int arr[10]={3,2,5,4,1,6,0,9,7,8};//创建整型数组
  int sz=sizeof(arr)/sizeof(arr[0]);
  print_arr(arr,sz);//打印排序前的数组
  qsort(arr,sz,sizeof(arr[0]),cmp_arr);//使用qsort
  print_arr(arr,sz);//打印排序后的数组
  return 0;
}

当我们会使用qsort后，还记得我上一篇文章写的使用冒泡排序吗？让我们用冒泡排序思想来模拟一下qsort函数吧！

#include<stdio.h>
#include<stdlib.h>
int cmp_arr(const void*e1,const void*e2)
{
  return *(int*)e1 - *(int*)e2;
  //如果向减，大于0，返回>0的值，说明左边元素大于右边元素，需要swap交换
  //小于0，返回<0的值，说明左边元素小于右边元素，不需要swap交换
  //等于0，返回=0的值，说明这俩个元素相同
}


void Swap(char* buf1,char* buf2,size_t width)
{
  int i=0;
  for(i=0;i<width;i++)
  {
    //这里的i<width，是为了让每个字节每个字节单独交换，因为我们并不知道每个元素有几个字节
    //如果是int 则4个字节，short，则2个字节，char，则1个字节
     int tmp = *buf1;
     *buf1 = *buf2;
     *buf2 = tmp;
     buf1++;
     buf2++;
  }
}


void bubble_sort(void* arr,size_t sz,size_t width,int (*cmp_arr)(const void* e1,const void* e2))
       //这一步是在模拟qsort函数，我们开头也有讲qsort每个参数的内容
       //width是我们设置的宽度，每个字节的宽度
{
  int i=0;
  int j=0;
  for(i=0;i<sz;i++)
  {
     for(j=0;j<sz-1-i;j++)
     {
        //这里和冒泡排序一样，但是接下来就有所差异
        if( (*cmp_arr) ( (char*)arr+j*width, (char*)arr+(j+1)*width ) >0 )
       //这里就是比较俩俩元素的大小，如果cmp_arr返回大于0的值，那么实现下面swap交换
         {
            Swap((char*)arr+j*width, (char*)arr+(j+1)*width)，width）;
         }
     } 
  }
}



void print_arr(int arr[],int sz)
{
  int i=0;
  for(i=0;i<sz;i++)
  {
     printf("%d ",arr[i]);
  }
     printf("\n");
}



int main()
{
  int arr[10]={4,2,3,1,7,5,6,0,8,9};
  int sz=sizeof(arr)/sizeof(arr[0]);
  print_arr(arr,sz);//打印排序前的数组
  bubble_sort(arr,sz,sizeof(arr[0]),cmp_arr);
  //还是用冒泡排序，但是我们来模拟qsort函数思想
  print_arr(arr,sz);//打印排序后的数组
  return 0;
}

这就是qsort的模拟，可能对新手的我们（包括我自己）会觉得复杂而又难，我也学习了三遍，学了好几天，才慢慢了解和学会，所以小伙伴们可以多分析代码，多回忆qsort每个参数的含义！！