模拟实现qsort函数：冒泡排序详解

GG Bond1

发布于 2024-06-14 20:47:40

520

发布于 2024-06-14 20:47:40

前言：

在C语言中，标准库提供了qsort函数用于对数组进行排序。qsort函数是一个通用的排序函数，可以根据用户提供的比较函数对数组进行排序。在本篇博客中，我们将介绍如何用冒泡排序模拟实现qsort函数的功能。首先，我们会详细介绍冒泡排序的原理和实现方式，然后演示如何用冒泡排序来模拟实现qsort函数

一、冒泡排序的原理

冒泡排序是一种简单直观的排序算法，其基本思想是通过相邻元素的比较和交换来实现排序。具体步骤如下：

从数组的第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们的位置，直到将最大的元素交换到数组末尾。
重复上述步骤，每次比较和交换都会将剩余元素中的最大值移动到正确的位置。
经过n-1次遍历后，数组就会按照从小到大的顺序排列。

冒泡排序的时间复杂度为O(n^2)，在大多数情况下并不是最优的排序算法，后面我们在学习了其他的排序后并不会经常用到它，但它的过程非常清晰，很适合初学者

二、模拟实现qsort函数

现在让我们开始模拟实现qsort函数，使用冒泡排序来对数组进行排序。首先，我们需要定义一个比较函数，用于指定排序的规则。比较函数的定义如下：

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

比较函数的作用是比较两个元素的大小关系，如果a小于b，则返回负值；如果a等于b，则返回0；如果a大于b，则返回正值。

接下来，我们实现冒泡排序函数bubbleSort，其参数包括待排序数组、数组元素个数、元素大小和比较函数。具体代码如下：

void Swap(char* e1, char* e2, int width)
{
    while (width--)
    {
        char tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
        e1++;
        e2++;
    }
}
void Bubble(void* a, int sz, int width,
    int(*cmp)(const void* , const void* ))
{
    for (int i = 0; i < sz-1; i++)
    {
        for (int j = 0; j < sz - i -1; j++)
        {
            if (cmp((char*)a + j * width, (char*)a + (j + 1) * width) > 0)
            {
                //满足条件就进行交换
                Swap((char*)a + j * width, (char*)a + (j + 1) * width, width);
            }
        }
    }
}

在bubbleSort函数中，我们使用冒泡排序算法对数组进行排序，通过比较函数指定排序规则，实现了模拟qsort函数的功能。

最后，在main函数中，我们可以测试我们模拟实现的qsort函数。具体代码如下：

int main()
{
    int a[] = { 2,5,3,7,8,4,9,1,0,6 };
    int sz = sizeof(a) / sizeof(a[0]);
    printf("排序前：");
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    Bubble(a, sz, sizeof(int), cmp);
    printf("排序后：");
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

在main函数中，我们定义了一个整数数组a，并调用bubbleSort函数对数组进行排序。最后，输出原始数组和排序后的数组，以验证排序的正确性。

三、完整代码示例

#include<stdio.h>
int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}
void Swap(char* e1, char* e2, int width)
{
    while (width--)
    {
        char tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
        e1++;
        e2++;
    }
}
void Bubble(void* a, int sz, int width,
    int(*cmp)(const void* , const void* ))
{
    for (int i = 0; i < sz-1; i++)
    {
        for (int j = 0; j < sz - i -1; j++)
        {
            if (cmp((char*)a + j * width, (char*)a + (j + 1) * width) > 0)
            {
                //满足条件就进行交换
                Swap((char*)a + j * width, (char*)a + (j + 1) * width, width);
            }
        }
    }
}
int main()
{
    int a[] = { 2,5,3,7,8,4,9,1,0,6 };
    int sz = sizeof(a) / sizeof(a[0]);
    printf("排序前：");
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    Bubble(a, sz, sizeof(int), cmp);
    printf("排序后：");
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

运行结果：