【排序算法】—— 冒泡排序

一、冒泡排序的原理

​ 冒泡排序法：（Bubble sort）是一种基础的交换排序，非常简单，一学就懂

​ 对数组进行遍历，每次对相邻两个进行比较大小，若大的数值在前面则交换位置（升序），完成一趟遍历后数组中最大的数值到了数组的末尾位置，再对前面n-1个数值进行相同的遍历，一共完成n-1次遍历就实现了排序完成

1. 第一趟对0~n-1遍历，依次对比前后的大小，若是不满足前小后大就交换，此时最大的数就被挪到了最后一个位置

2. 对0~n-2遍历，继续比较前后大小，此时前n-2个数中最大的数就到了倒数第二个位置

3. 重复上述动作继续遍历，每一次都将最大的数向后挤，直到遍历完毕排序成功

二、代码实现

​ int类型数组的升序排序的简单实现

void bubble_sort(int* arr, int length)
{
    int i = 0;
    for (i=0; i<length-1; i++)			//遍历n-1次
    {
        int j = 0;
        for (j=0; j<length-1-i; j++)	//相邻两个数据依次进行比较
        {
            if (arr[j] > arr[j+1])		//顺序不对的交换位置
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

三、代码的优化

如果一次遍历，没有数据进行交换，则证明数组已经排好了顺序，不需要继续遍历，则引入flag变量标志记录第一次遍历是否有数据交换

void bubble_sort(int* arr, int length)
{
    int i = 0;
    for (i=0; i<length-1; i++)
    {
        int flag = 0;				   //flag标识
        int j = 0;
        for (j=0; j<length-1-i; j++)
        {
            if (arr[j] > arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;				//发生数据交换，置flag为1
            }
        }
        if (flag == 0)					//若flag为0，则没有发生交换，跳出循环
        {
            break;
        }
    }
}

四、冒泡排序的效率

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(1)$

冒泡排序是稳定的排序算法（相同数据排序时不会影响原来的顺序，对结构体类型有影响）

五、模仿库函数的qsort实现

​ C语言中库函数qsort是通过函数指针cmp传入数据类型的比较方式，实现对各种数据类型都能进行排序的功能

​ 我们将模仿qsort函数使用冒泡排序算法实现对各种数据类型都能进行排序的函数，并且使用const关键字严格限制参的属性，达到很高的健壮性要求

1. 相关接口

1. 冒泡排序函数：

void bubble_sort(const void* base, const int length, const int size, int (*cmp)(void* e1, void* e2));

• 参数：
  1. base：被排序的数组，由void*类型指针接收，const不能改变指针指向的内容，但可以改变指针的指向
  2. length：数组的长度，就是值的数量，由const限制不能改变大小
  3. size：数组中存放的数值类型的字节大小，就是一个值占几个字节的空间，由const限制不能改变大小
  4. cmp：数组中数据的比较规则，由cmp函数指针接收

2. 交换数据函数：

​ 将指针转换成char*，依次按照字节进行交换

void Swap(const void* e1, const void* e2, const int size);

• 参数：
  1. e1：被交换的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容
  2. e2：被交换的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容
  3. size：被交换数据类型的字节大小，由const限制不能改变大小

3. 比较函数：数组中数值的比较规则

int cmp(const void* e1, const void* e2);

• 返回值：大于0，e1大；等于0，一样大；小于0，e2大
• 参数：
  1. e1：被比较的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容
  2. e1：被比较的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容
• 函数体：
  • 由用户自定义实现数值的比较规则

传参：

1. 被比较数值的地址由void*指针接收

2. 数值在数组中第 i 个位置：将void*转换成char指针，(char*)base + i*size

一些比较规则的演示：

//int类型数据比较（升序）
int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}

//int类型数据比较（降序）
int cmp(const void* e1, const void* e2)
{
    return *(int*)e2 - *(int*)e1;	//降序就是把e1，e2的位置交换一下
}

//字符串比较（按字母升序）
#include <string.h>
int cmp(const void* e1, const void* e2)
{
    return strcmp((char*)e1, (char*)e2);	//其实有点多余，直接把strcmp传入bubble_sort中就行了
}

2. 代码实现

1. 冒泡排序法的实现：

#include <assert.h>		//引入头文件<assert.h>，使用assert函数断言

//交换数据
void Swap(const void* e1, const void* e2, const int size)
{
    assert(e1!=NULL && e1!=NULL && size>0);		//断言判断各个参数的合法性
    
    int i = 0;
    for (i=0; i<size; i++)
    {
        char temp = *((char*)e1 + i);
        *((char*)e1 + i) = *((char*)e2 + i);
        *((char*)e2 + i) = temp;
    }
}

//冒泡排序法
void bubble_sort(const void* base, const int length, const int size, int (*cmp)(const void* e1, const void* e2))
{
    assert(base!=NULL && length>0 && size>0 && cmp!=NULL);		//断言判断各个参数的合法性
    
    int i = 0;
    for (i=0; i<length-1; i++)
    {
        int flag = 0;
        int j = 0;
        for (j=0; j<length-1-i; j++)
        {
            if (cmp((char*)base + j*size, (char*)base + (j+1)*size) < 0)	//比较数据大小
            {
                Swap((char*)base + j*size, (char*)base + (j+1)*size, size);		//交换数值
                flag = 1;
            }
        }
        if (flag == 0)
        {
            break;
        }
    }
}

2. 字符串数组升序排序的演示：

#include <stdio.h>
#include <string.h>
int test1(void)
{
    char* strs[] = {"abc", "def", "bpm", "jqx"};
    bubble_sort(strs, sizeof(strs), sizeof(char*), strcmp);
    //printf打印排序之后的内容
}

3. 整型数组降序排序的演示：

#include <stdio.h>

//整型降序比较函数
int cmp_int(void* e1, void* e2)
{
    return *((int*)e2) - *((int*)e1);
}

//测试函数，用于调用排序函数
int test2(void)
{
    int nums[] = {2, 5, 8, 7, 1, 6};
    bubble_sort(strs, sizeof(nums), sizeof(int), cmp_int);
    //printf打印排序之后的内容
}