深入理解C语言中冒泡排序（优化）

目录

引言：

?冒泡排序概述：

优化前：

优化后(注意看注释)：

解析优化后：

原理（先去了解qsort）：

---

引言：

????????排序算法是计算机科学中的基础问题之一。在本篇博客中，我们将深入研究C语言中排序算法的实现原理，特别关注优化过的冒泡排序。此外，我们会详细讨论函数指针的概念，以及如何使用函数指针实现通用的排序函数。

?冒泡排序概述：

????????冒泡排序是一种简单而直观的排序算法。其基本思想是通过多次遍历待排序数组，比较相邻元素并交换，直到整个数组有序。下面是优化前/优化后的冒泡排序的实现：

优化前：

// 定义一个冒泡排序函数，参数为一个整数指针和数组大小
int paixu(int* arr, int sz) {
    // 外层循环控制遍历次数，每次遍历都会将最大（或最小）的元素移动到末尾
    for (int i = 0; i < sz - 1; i++) {
        // 内层循环用于比较和交换相邻的元素
        for (int j = 0; j < sz - 1 - i; j++) {
            // 如果前一个元素小于后一个元素，则交换它们的位置
            if (arr[j] < arr[j + 1]) {
                // 使用异或操作实现无临时变量的交换
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
            }
        }
    }
}

int main() {
    // 初始化一个包含10个元素的数组
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    // 计算数组的大小
    int sz = sizeof(arr) / sizeof(arr[0]);
    
    // 调用冒泡排序函数对数组进行排序
    paixu(arr, sz);

    // 输出排序后的数组元素
    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

????????这个程序定义了一个冒泡排序函数`paixu`，并在一个`main`函数中使用该函数对一个整数数组进行排序。冒泡排序通过不断地比较和交换相邻的元素，将最大的（或最小的）元素逐步移动到数组的末尾。这里使用了异或操作来实现元素的交换，无需额外的临时变量。在主函数中，我们初始化了一个数组，计算其大小，并调用`paixu`函数进行排序，最后输出排序后的数组元素。

这个程序只能排序数组下面我们优化一下这个冒泡排序让他可以排序其他的数据

优化后(注意看注释)：

// 定义一个比较函数，接收两个void*类型的指针作为参数，返回它们指向的int值的差
int compare(const void* a, const void* b)
{
    // 解引用指针并进行减法操作
    return (*(int*)b - *(int*)a);
}

// 定义一个stu结构体，包含姓名和年龄
struct stu
{
    char name[20];
    int age;
};

// 定义一个新的比较函数，用于比较stu结构体的年龄成员
int compar(const void* p1, const void* p2)
{
    // 解引用指针并获取age成员，然后进行减法操作
    return ((struct stu*)p1)->age - ((struct stu*)p2)->age;
    
    // 如果需要按照姓名升序排序，可以使用strcmp函数（注意：这将按ASCII值排序，不适用于非ASCII字符）
    // return strcmp(((struct stu*)p2)->name, ((struct stu*)p1)->name);
}

// 定义一个交换函数，用于交换两个内存区域的内容
void exchange(char* a1, char* a2, int sz) 
{//char(一个字节)，把sz(元素大小)传过来就可以确定有多少个char*    如果传过来的是4个字节char*接收一个字节，所以把宽度传过来利用循环一个一个的交换
    // 使用循环，根据元素大小sz逐个交换元素
    for (int i = 0; i < sz; i++)
    {
        char tmp = *a1;
        *a1 = *a2;
        *a2 = tmp;
        a1++;
        a2++;
    }
}

// 定义一个优化的冒泡排序函数
void effervescence(void* base, int num, int sz, int (*pa)(void* p1, void* p2)) 
{
    // 使用两层循环进行冒泡排序
    for (int i = 0; i < num - 1; i++)
    {
        for (int j = 0; j < num - 1 - i; j++) 
        {
            // 根据元素大小sz计算索引，并调用比较函数
            if (pa((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
            {
                // 如果前一个元素大于后一个元素，交换它们 //(char*)base+sz -- 将起始强制转换(char*)+sz(元素大小)
                exchange((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);如果j是[0 -- 0，1] [1 -- 1，2] [2 -- 2，3] 
            }
        }
    }
}

// 测试结构体数组排序
void text1() 
{
    struct stu s1[3] = { {"mdxx",10},{"mxxmm5",20},{"sss",25} }; // 初始化结构体
    int num = sizeof(s1) / sizeof(s1[0]); // 计算结构体数组长度
    int sz = sizeof(s1[0]); // 计算元素长度
    effervescence(s1, num, sz, compar); // 对结构体数组进行排序
    for (int i = 0; i < num; i++) 
    {
        printf("Name: %s, Age: %d\n", s1[i].name, s1[i].age);
    }
}

// 测试整数数组排序
void text2() 
{
    int arr[] = { 2,5,4,7,8,9,0,1,6 };
    int num = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
    int sz = sizeof(arr[0]); // 计算元素长度
    effervescence(arr, num, sz, compare); // 对整数数组进行排序
    for (int i = 0; i < num; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() 
{
    text1(); // 调用结构体数组排序测试
    text2(); // 调用整数数组排序测试
    return 0;
}

????????这段代码包含了两个比较函数（compare和compar）、一个交换函数（exchange）和一个优化的冒泡排序函数（effervescence）。通过传入不同的比较函数和数据类型，可以对不同类型的数组或结构体数组进行排序。

解析优化后：

首先，我们来看一下基础的比较函数。这里有两个比较函数：compare 和 compar。

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

struct stu
{
    char name[20];
    int age;
};

int compar(const void* p1, const void* p2)
{
    return ((struct stu*)p1)->age - ((struct stu*)p2)->age;
   }

???compare 函数用于比较两个整数值，而 compar 函数用于比较两个 stu 结构体的年龄成员。

我们定义一个交换函数 exchange，用于交换两个内存区域的内容：

void exchange(char* a1, char* a2, int sz) 
{
    for (int i = 0; i < sz; i++)
    {
        char tmp = *a1;
        *a1 = *a2;
        *a2 = tmp;
        a1++;
        a2++;
    }
}

????????这个函数接收两个指针 a1 和 a2 以及元素大小 sz，然后逐个交换这两个内存区域的元素

我们来看看优化的冒泡排序函数 effervescence：

void effervescence(void* base, int num, int sz, int (*pa)(void* p1, void* p2)) 
{
    for (int i = 0; i < num - 1; i++)
    {
        for (int j = 0; j < num - 1 - i; j++) 
        {
            if (pa((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
            {
                exchange((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
            }
        }
    }
}

????????这个函数接收一个基础指针 base、元素数量 num、元素大小 sz 以及一个指向比较函数的指针 pa。它通过两层循环进行冒泡排序，并在需要时调用 exchange 函数交换元素。

最后，我们编写两个测试函数 text1 和 text2，分别用于测试结构体数组和整数数组的排序：

void text1() 
{
    struct stu s1[3] = { {"mdxx",10},{"mxxmm5",20},{"sss",25} };
    int num = sizeof(s1) / sizeof(s1[0]);
    int sz = sizeof(s1[0]);
    effervescence(s1, num, sz, compar);
    for (int i = 0; i < num; i++) 
    {
        printf("Name: %s, Age: %d\n", s1[i].name, s1[i].age);
    }
}

void text2() 
{
    int arr[] = { 2,5,4,7,8,9,0,1,6 };
    int num = sizeof(arr) / sizeof(arr[0]);
    int sz = sizeof(arr[0]);
    effervescence(arr, num, sz, compare);
    for (int i = 0; i < num; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

这个优化的冒泡排序算法可以根据传入的不同比较函数和数据类型，对不同类型的数组或结构体数组进行排序。

原理（先去了解qsort）：

????????冒泡排序的基本原理是通过不断地遍历待排序的列表，并在每次遍历时比较相邻的元素，如果它们的顺序错误（即，前一个元素大于后一个元素），则交换这两个元素的位置。这个过程会重复进行，直到整个列表都被排序。

在原始的冒泡排序算法中，每一轮遍历都会确保最大的元素被“冒泡”到当前未排序部分的末尾。但是，当列表已经部分排序时，这种简单的冒泡方法效率较低，因为它仍然会对已排序的部分进行不必要的比较和交换。为了优化冒泡排序，我们可以引入一个额外的变量来记录最后一次发生交换的位置。在后续的遍历中，我们可以忽略已排序的部分，只需要遍历到上次发生交换的位置即可。这样可以减少不必要的比较和交换，从而提高排序效率。

在我们的 `effervescence` 函数中，我们使用了两层循环来实现冒泡排序：

????????1. 外层循环：控制总共需要进行多少轮遍历。初始情况下，我们需要进行 n-1 轮遍历，其中 n 是列表的长度。
????????2. 内层循环：在每一轮遍历中，比较相邻的元素并进行必要的交换。如果发生了交换，我们将更新上次发生交换的位置。

????????通过使用指向比较函数的指针，我们可以根据不同的数据类型和排序需求提供相应的比较逻辑。在 `text1` 和 `text2` 测试函数中，我们分别提供了对结构体数组和整数数组进行排序的比较函数。

????????在 `compar` 函数中，我们比较了两个 `stu` 结构体的年龄成员，以按照年龄从小到大进行排序。而在 `compare` 函数中，我们直接比较了两个整数值的大小，实现了整数数组的升序排序。

? ? ? ? 注意看代码的注释，其中原理和qsort函数一样?和一些函数回调，大家慢慢理解其中逻辑，我的文章不解释过多的基础，谅解