目录
假设你是一名教官，站在你面前的有身高不同的一组人，你的任务就是用最短的时间将他们按从矮到高依次排好一列，你会选择怎么办？
假如你恰好懂得冒泡排序，那么恭喜你，你就多了一种对数据进行排序的方法，也就恰好可以处理这个问题.
冒泡排序，按照名字来理解，假如水中存在气泡，它总是会浮向水面
假如我们要排序的数据（按升序来举例）
永远将一组数中最大的数当成泡泡，经过一次循环后，它将到达最后的位置，然后循环次数的增加，逐渐把最大的数放到最后，自然而然，就对整个数组完成了升序排列.
下面我们根据实例来加深理解
假设一开始数字排序为9 8 7 6 5 4 3 2 1，我们要对它进行升序排序
9是整个数组的最大值，它就是第一趟循环的泡泡，通过两两比较交换位置，最终它必然会到达最后的位置.(形象点说，浮出水面).
当9排到数组的最后面时，我们就不会再对它进行处理.
这时候在剩下的数字里面，8是整个数组的最大值，它就是我们第二趟循环的泡泡，通过两两比较交换位置，最终它也必然会到达最后的位置.
类似这样，假设有n个数，经过n - 1趟排序(最后剩下一个数，不需要进行排序),就可以完成对整个数组的升序排序.
二.冒泡排序的实现(升序)
既然我们已经有了思路，就可以开始着手实现了.
1.首先我们解决的是找泡泡的问题，怎样保证经过每次循环的时候，最后面放的都是最大的数据呢?
经过一番思索后，我们可以采取两两比较的方法
只要比后面的数字大，就互换两个数的位置
比如4 7 6 3
4比7小，不互换两个数的位置;? 4 7 6 3
7比6大,? 互换两个数的位置;? ? ? 4 6 7 3
7比3大，互换两个数的位置.? ? ? 4 6 3 7
2.接下来解决趟数的问题，经过上面的举例，我们可以发现，一趟可以解决1个数字（泡泡），那假设有n 个数字，则需要n - 1趟.
3.每趟循环，都需要两个数字两两比较吗？前面我们已经提到过，原先的泡泡是完全不用理会的，它已经摆在正确的位置上了，可以进行比较，但相应时间就会被浪费.有9个数字就比较8次，有8个数字就只用比较7次即可.
?看上去程序已经很完美了，但我们需要知道，当数字很多的时候，对于冒泡排序而言，其时间复杂度可不低，最坏情况有O(n^2).
所以,我们还要思考到，假如在一趟排序中，我们已经把数组升序排列了，我们还要进行后续的操作吗？显然是没有必要的.
因此我们再对其进行一些修改，设立一个哨兵flag =1,代表为有序，假如没有交换数字了，flag始终为1，那我们就可以相应跳出循环.
void bubble_sort(int arr[],int sz)//sz表示数组中的元素个数
{
for (int i = 0; i < sz - 1; i++)//sz - 1趟
{
int flag = 1;//哨兵为1，代表数组已经有序
for (int j = 0; j < sz - 1 - i; j++)//每次循环只需要比较sz - 1 - i次
{
if (arr[j] > arr[j + 1])//两个数满足前大于后，交换位置
{
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
flag = 0;
}
}
if (flag) break;
}
}?三.qsort函数介绍
我们已经会编写冒泡排序函数了，但美中不足的是，我们只能用它对整型进行排序，而字符串，结构体的比较，则不能实现，我们能否对其进行修改呢？
C语言库函数中有一个函数叫作qsort的函数，它能提供任意类型的数据比较排序，虽然它实现的底层原理是快速排序，但我们依旧可以根据它，对我们的冒泡排序进行改造.
首先，我们对qsort函数进行了解. (去cplusplus.com了解)
接下来，我们看看qsort函数的参数解释.
函数指针，qsort函数是有相应规定的.
p1指向的元素大于p2指向的元素，则返回大于0d的数；反之若小于，则返回小于0的数?
下面是对qsort函数使用的测试程序，可以cv到编译器底下，自己运行下，加深理解.
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
//测试qsort排序结构体
int cmp_by_name(const void* p1, const void* p2)
{
return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void test3()
{
struct Stu s[] = { {"wangwu",20},{"zhangsan",30},{"lisi",55} };
//按照名字比较
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_by_name);
}
//测试qsort排序整型
int cmp_int (const void* p1, const void* p2)
{
return (*(int*)p1 - *(int*)p2);
}
void test2()
{
int arr[] = { 2,1,3,4,2,3,5,8,7,4,9 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
Print(arr, sz);
}四.冒泡排序改造
首先，按照qsort函数参数的启发，我们可以知道，我们的bubble_sort函数也需要进行相应的参数改造(毕竟要排任意类型的数据)
?然后我们仔细思索后会发现，需要改造的地方仅仅在于两个元素判断大小的方法需要改变，以及交换的方式需要改变，毕竟我们无法确定用户需要我们改造后的bubble_sort函数比较什么类型的数据.
对于前者(判断大小的方法)，我们有函数指针传进来，只需要正确表示，然后传入需要比较的两个元素的地址即可
如何正确表示两个元素的地址呢？我们知道base，也就是刚开始的地址(指针)，指针加步长便可进行相应的移动，指向相应的元素地址.
注意：要先将base转成char*类型，void*类型不能进行指针移动(那为什么不转成其它类型呢？width是一个元素所占字节大小,转成char*类型，+width恰好可以指向不同元素)
对于后者(交换的方式),不同数据所占的空间实际上是不同的，我们也不能像当初一样简单的，就创建一个int类型的临时变量，然后进行交换.
但我们意识到，所有数据在内存中都是一个个字节进行存储的，如果我们循环width(每个元素所占字节大小)次，对每个字节里的内容进行交换，不就可以完成元素的交换？
至此，我们便对bubble_sort函数完成了改造，完整代码如下：
void Swap(char *buf1,char* buf2,int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* p1, const void*p2))
{
for (int i = 0; i < sz - 1; i++)
{
int flag = 1;
for (int j = 0; j < sz - 1 - i; j++)
{
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交换
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
flag = 0;
}
}
if (flag) break;
}
}?至此，传入相应的函数指针，即比较元素大小的方法，我们改造后的bubble_sort函数便可以像qsort函数一样，比较任意类型的数据.