C语言：qsort模拟实现

qsort函数是C语言中的一个标准函数，用于对数组进行快速排序。其函数原型如下：

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

参数解释：

• base：指向数组首元素的指针。
• nmemb：数组的元素个数。
• size：每个元素的大小（以字节为单位）。
• compar：比较函数的函数指针。

compar函数用于定义元素之间的比较规则。它需要返回一个整数值，表示两个元素之间的关系。具体的返回值规则如下：

• 如果*ptr1 < *ptr2，则返回一个负整数。
• 如果*ptr1 == *ptr2，则返回0。
• 如果*ptr1 > *ptr2，则返回一个正整数。

使用示例：

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
int main()
 {
    int arr[] = {5, 2, 8, 10, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, n, sizeof(int), compare);
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

上述示例中的compare函数用于比较两个整数值。main函数中创建了一个整型数组，并调用qsort函数对其进行排序。最后，通过遍历数组打印出排序后的结果。

输出结果为：

1 2 5 8 10

qsort函数是C标准库中提供的用于快速排序的函数。通过传入一个比较函数，可以对任意类型数组进行排序。使用前需要引入stdlib.h头文件。

也许你现在有点迷惑，为什么这个qsort函数设计的这么麻烦，接下来我们来实现一个qsort函数，帮助大家理解。

冒泡排序版

鉴于大部分同学学习指针的时候，还没有学习过快速排序，所以我这里用冒泡排序进行代替。

先看到一个基本的冒泡排序：

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void bubble(int* arr,int sz)
{
  for (int i = 0; i < sz; i++)
  {
    for (int j = 0; j < sz - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}

这个排序有以下缺陷：

1. 只能排int类型的数据
2. 只能排升序

qsort的实现就是围绕解决这两个问题。

Swap - 交换函数

首先，如果用户要传入不同类型的数据，每种数据占用的字节不同，请问如何实现数据的交换？

想要在函数内部实现函数外部的变量的数据交换，那就需要传址调用，这是毫无疑问的。但是我们的Swap函数要如何接收各种数据类型的指针？

答案毫无疑问就是使用void*类型的指针，使用void*类型的指针，可以接收任何类型的指针，唯一的缺点就是不能解引用。void*类型的指针在解引用之前必须要强制类型转换，这下完了，我们不知道转化为什么类型的指针。

换一个思路，为什么我们一定要直接交换两个数据呢？现在我们可以利用void*类型的指针来接收待交换的两个变量的指针，内存中的数据是以字节存储的，我们可不可以一个一个字节进行交换，然后在外部传入这种变量类型的字节长度，从而知道要交换几个字节？

思路理清后，我们看看Swap需要的参数：

void Swap(void* p1, void* p2, int size)

• p1和p2，待交换的两个变量的指针
• size待交换的变量的类型所占字节数

接下来我们就要实现交换函数的内部了。

既然void*类型的指针需要强制转化后才能解引用，而我们要一个一个字节地交换数据。那是不是我们可以把这个指针强制转化为一个访问权限为一字节的指针，也就是char*类型？

强制转化完后，再一个一个字节的交换，而交换的次数就是这个类型所占的字节数size。

代码如下：

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

cmp - 比较函数

我们需要排序本体也对多种数据进行排序，但是int类型比大小是比较数据的大小；字符串比大小是比字典序；外加我们有时候需要升序，有时候需要降序。如何让我们的排序在比大小的时候可以匹配任意规则呢？

为此，qsort的设计者将比较权限交给了使用者，也就是说用户可以自定义数据的比较规则。这是怎么做到的？

这得益于回调函数。用户可以把比较规则写在函数种，然后把函数当作参数传递给排序主体，这样qsort就知道如何排序了。这个函数一般叫做cmp即compare的缩写。

假设我们的待比较的元素是e1和e2。

首先，cmp给了一个基本规定：

• 当 e1 > e2 返回值大于0
• 当 e1 = e2 返回值等于0
• 当 e1 < e2 返回值小于0

接下来我们讨论如何做一个回调函数的指针参数：

函数指针做参数有一个缺点，那就是指针类型是写死的。

如果用户要比较两个int类型数据，用户会这样写：int cmp(int x, int y);；

此函数的指针类型为int (*)(int, int);

但是如果比较float的数据，那就会这样写：int cmp(float x, float y);；

此函数的指针类型为int (*)(float, float);

函数指针类型不一样，这不利于统一处理函数。那么如何让cmp函数可以接收任何类型的数据呢？此时void*类型的指针又上场了，为了避免数据类型问题，我们干脆不传值了，直接传void*指针来统一处理数据。

于是qsort规定：所有人自己在写cmp函数的时候，两个待比较的参数必须是void*类型。返回值必须是int类型，以及： 当 e1 > e2 返回值大于0；当 e1 = e2 返回值等于0；当 e1 < e2 返回值小于0。

至此，我们就可以确定我们的回调函数指针类型就是int (*)(void*, void*)了，那实现cmp函数的人又要怎么办呢？

看到以下cmp函数：

int int_cmp(void* e1, void* e2)
{}

假设我们要比较两个int类型的数据，现在我们得到了两个void*类型的指针，分别指向两个数据，要如何比较呢？

答案当然是：先强制转化为int*类型的指针，然后再比较。

比如这样：

int int_cmp(void* e1, void* e2)
{
  int ret = *(int*)e1 - *(int*)e2;
  return ret;
}

(int*)e1是在对void*类型的指针进行类型转化，转化完成后再解引用，所以是*(int*)e1。e2同理。

而qsort对返回值的规定，我们直接让两数相减即可。==如果你想排逆序，那么交换e1和e2的位置即可：

int int_cmp(void* e1, void* e2)
{
  return  *(int*)e2 - *(int*)e1;//逆序排序
}

qsort - 排序主体

我们原本的冒泡排序主体如下：

void qsort(int* arr,int sz)
{
  for (int i = 0; i < sz; i++)
  {
    for (int j = 0; j < sz - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}

由于传入的数据不一定是int类型，是不确定的，结合之前的经验，这里多半要传入一个void*类型的指针。

我们看看最终版本的qsort的参数：

void qsort(void* base, int nmemb, int size, 
      int(*cmp)(const void*, const void*))

• base，即传入的待排序数组，用void*接收，以适应不同类型数据
• nmemb 这个数组的元素个数，防止越界访问
• size 待排序的变量类型，所占用的字节数（Swap种需要知道这个变量占几个字节）
• cmp 即用户自定义的比较函数，这里统一了类型为int (*)(void*, void*)，用户使用时要用这种类型的函数

我们先前已经优化了用于比较的cmp函数，接下来就是把原来函数种比较的大于小于号，改成利用cmp函数比较：

原本的比较：

if (arr[j] > arr[j + 1])

现在我们有指向数组的指针base，指针偏移量j，单个元素占用的字节数size，以及用于比较的函数cmp。

首先要定位到当前j指向的元素，对于平时的访问，我们直接*(base + j)即可，但是我们的base是void*类型的指针，不能解引用。与上一次相同，既然我们知道了一个变量占几个字节，我们干脆都统一为cahr*类型，一个一个字节来处理。

所以要先把base转化为char*：(cahr*)base。随后跳过j个变量，一个变量占size个字节，那就需要跳过j * size个字节，因此目标元素的地址为：(char*)base + (j * size)。

现在我们要往cmp函数里面传入j和j + 1位置的元素的地址，所以cmp的调用为：

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

如果cmp的返回值大于0，则说明要交换，所以if语句如下：

if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
  //Swap
}

如果满足要求，需要利用Swap交换，传参与cmp是同理的：

if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
  Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}

接下来看一下完整的代码：

void Swap(void* p1, void* p2, int size)
{
  for (int i = 0; i < size; i++)
  {
    char tmp = *((char*)p1 + i);
    *((char*)p1 + i) = *((char*)p2 + i);
    *((char*)p2 + i) = tmp;
  }
}
void qsort(void* base, int nmemb, int size, int(*cmp)(const void*, const void*))
{
  for (int i = 0; i < nmemb - 1; i++)
  {
    for (int j = 0; j < nmemb - i - 1; j++)
    {
      if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
      {
        Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
      }
    }
  }
}

当我们需要调用这个qsort对double类型的数据进行排序，我们要写以下代码：

int cmp(const void* e1, const void* e2)
{
  return (*(double*)e1 - *(double*)e2);
}
int main()
{
  double arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
  qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(double), cmp);
  
  return 0;
}

首先我们自己写一个double类型数据的比较规则：

int cmp(const void* e1, const void* e2)
{
  return (*(double*)e1 - *(double*)e2);
}

然后传参：qsort(数组指针, 数组长度, 该类型数据占用字节, 自己写的比较函数)

qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(double), cmp);

至此，你应该明白了为什么我们要这样写qsort函数，以后利用qsort进行排序，也就更清楚的知道每一步，每一个参数是干什么用的了。