【C语言】剖析qsort函数的实现原理

回调函数

什么是回调函数？

回调函数实际上是一个指针，指向的是一个函数。它作为一个参数传递给另一个函数，并且在特定的条件下被执行。

回调函数的作用

回调函数的主要作用是使代码更加灵活和模块化。通过使用回调函数，我们可以将特定的行为或逻辑与原始函数分离开来，这样可以让我们更容易地进行代码重用和维护。

回调函数的实现

定义一个函数，然后将其作为参数传递给其他函数，在特定条件下执行

回调函数的示例

让我们以 C 语言为例，来看一个简单的回调函数示例：

#include <stdio.h>
void performOperation(int a, int b, int (*callback)(int, int))
{
    int result = callback(a, b);
    printf("The result is: %d\n", result);
}
int add(int a, int b)
{
    return a + b;
}
int main()
{
    int x = 10, y = 20;
    performOperation(x, y, add);  // 传递 add 函数作为回调函数
    return 0;
}

在这个示例中，performOperation 函数接受两个整数和一个函数指针作为参数，然后在内部调用传递进来的函数指针，实现了加法运算。在主函数中，我们将 add 函数作为回调函数传递给 performOperation 函数。这就是一个简单的回调函数的例子。

qsort函数的应用

函数定义

在官方文档中qsort的函数定义如下：

void qsort (void* base, size_t num, size_t size,

               int (*compar)(const void*,const void*));

函数参数的剖析

base：

参数base是一个void* 类型的，qsor使用来排序的函数，该参数就是传入的要进行排序的数组。作为一个void*类型的指针，我们传入数组的地址，即可完成对要排序数组的传入。

num：

该参数位置要传入的是要进行排序的数组的元素个数，一般使用sizeof（数组名）/ sizeof（数组中的任意元素）进行计算得到个数。

size：

参数size传入的参数是数组中单个元素的大小，该参数可以确保在函数内排序的时候每次跳跃的字节大小是一个元素的字节的大小。

compar:

该参数是一个函数指针，指向比较两个元素的函数。 qsort内部会反复调用此函数来比较两个元素，以此来决定排序方向。

请注意！在传入该参数的时候请严格按照该参数的规范结构来书写。

int (*compar)(const void*,const void*)

为什么要用void*？

这是因为 qsort 函数可以对任意类型的数组进行排序，而不同类型的数据可能需要不同的比较方法。使用 void* 类型作为参数可以让比较函数更加通用，因为 void* 是一种无类型指针，可以指向任何类型的数据。在比较函数内部，我们可以将 void* 类型的指针转换为实际的数据类型再进行比较（强制类型转化）。

通过使用 void* 类型，可以在不知道具体数据类型的情况下编写通用的比较函数，使 qsort 函数更加灵活和通用。在比较函数中，我们需要负责将 void* 类型的指针转换为实际的数据类型，并进行比较操作。

使用 void* 类型的参数可以使比较函数更加通用，适用于不同类型的数据，从而增强了函数的灵活性和通用性。

经典代码示例

#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于升序排序
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // 使用 qsort 对数组进行排序
    qsort(arr, n, sizeof(int), compare);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

在这个示例中，首先定义了一个整型数组 arr，然后通过 qsort 函数对数组进行排序。在 main 函数中，我们计算数组的大小 n，然后调用 qsort 函数，传入数组、数组大小、每个元素的大小以及比较函数 compare。比较函数 compare 中，我们将 void* 类型的指针转换为 int* 类型，并进行升序排序。最终得到的就是升序排序的数组了。

qsort函数实现原理

详细定义

qsort 函数是一个用于快速排序（Quick Sort）的标准库函数。它接受一个数组和一个比较函数作为参数，并对数组进行排序。快速排序是一种分治的排序算法，通过选择一个基准元素，将数组分为两部分，一部分比基准元素小，一部分比基准元素大，然后对这两部分递归地进行排序，最终得到一个有序的数组。

实现原理

1. 选择基准元素：qsort 函数首先选择数组中的一个元素作为基准元素。通常情况下，可以选择数组的第一个元素作为基准元素。
   
2. 分区（Partition）：qsort 函数使用选定的基准元素将数组分为两部分，一部分小于等于基准元素，另一部分大于基准元素。这个过程称为分区。
   
3. 递归排序：qsort 函数递归地对小于等于基准元素和大于基准元素的两部分进行排序。它分别对这两部分调用 qsort 函数，并将相应的比较函数传递给子函数。
   
4. 合并结果：最后，qsort 函数将排序后的两部分合并起来，形成一个有序的数组。
   

模拟实现sort

以下代码使用C语言模拟实现qsort函数的代码：

#include <stdio.h>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
void myQsort(int arr[], int n) {
    quickSort(arr, 0, n - 1);
}
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    myQsort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

这是一个以快速排序为基础的qsort函数实现，通过选择一个基准元素，并将数组分成两部分，使得左边的元素都小于或等于基准元素，而右边的元素都大于基准元素，然后对左右两部分递归地进行排序，最终得到一个有序的数组。

以下是各个函数的分解解析：

1. swap 函数：这个函数用于交换两个整数的值。它接受两个整数指针作为参数，并使用 temp 变量来暂存其中一个整数的值，然后将两个整数的值进行交换。
2. partition 函数：这个函数用于将一个数组的某个子数组分成两部分，使得左边的元素都小于或等于基准元素，而右边的元素都大于基准元素。它接受一个整数数组、子数组的起始索引和结束索引作为参数。首先，它选择最后一个元素作为基准元素，并将 i 初始化为 low - 1。然后，它使用一个循环从 low 到 high - 1 遍历数组，如果当前元素小于基准元素，就将 i 向右移动一个位置，并将当前元素和 arr[i] 进行交换。最后，它将基准元素和 arr[i + 1] 进行交换，使得基准元素位于正确的位置上。
3. quickSort 函数：这个函数用于对一个数组进行快速排序。它接受一个整数数组和起始索引和结束索引作为参数。如果起始索引小于结束索引，它就调用 partition 函数将数组分成两部分，并对左右两部分递归地进行排序。
4. myQsort 函数：这个函数是一个封装的快速排序函数，它接受一个整数数组和数组的大小作为参数，并调用 quickSort 函数对数组进行排序。
5. main 函数：这个函数是程序的入口函数。它首先定义了一个整数数组 arr，并计算数组的大小。然后，它调用 myQsort 函数对数组进行排序，并打印排序后的结果。

本篇博客到此就结束啦~

如果有帮助到您的学习是我的无上荣幸！

感谢阅读！