文章目录
- 冒泡排序
- 普通版本
- 对外层循环进行优化
- 对内循环进行优化
- 双向冒泡排序
- qsort函数
- 分析与使用
- 模拟实现qsort函数
冒泡排序
当我们第一次提起冒泡排序的时候，我们总是要问什么是冒泡排序呢？
简单的说，就是重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
而这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
普通版本
我们先对整数类型的数据进行排序，比如我们要排 5 6 1 3 4 2 7 8 这8个数字，令它们变成有序数组。
图片分析如下：
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void BubbleSort(int* p, int sz)
{
int i = 0, j = 0;
for (int i = 0; i < sz - 1; i++) //比较的总趟数为元素个数减1
{
//控制每一趟过程比较的个数
//每一趟结束后，下一趟比较的最后一个元素就是前面那一位
for (int j = 0; j < sz - 1 - i; j++)
{
//前面元素大于后面元素就交换
if (p[j] > p[j + 1])
{
int tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
}
}
}
}
void Print(int* p, int sz) //打印数组内的元素
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", p[i]);
}
printf("\n");
}
int main()
{
//用两个数组来验证
int arr[] = { 5,6,1,3,4,2,7,8 };
int arr2[] = { 10,9,8,7,6,5,4,3,2,1 };
//求出数组内的元素个数为sz
int sz = sizeof(arr) / sizeof(arr[0]);
int sz2 = sizeof(arr2) / sizeof(arr2[0]);
//排序数组arr
BubbleSort(arr, sz); //普通的冒泡排序
Print(arr, sz); //打印函数
//排序数组arr2
BubbleSort(arr2, sz2);
Print(arr, sz);
return 0;
}
程序执行结果如下： 
对外层循环进行优化
大家请先看第三轮到最后一轮的排序：
不知道大家发现一个问题没有，上面从第四趟开始就已经是有序的了，但是我们的程序还是要跑一次，我们可以从这个地方入手来优化。
思路如下：
我们可以设一个变量flag等于0，在每一趟过程中；如果程序验证到前面的数比后面的数大，说明数组还没有序，并且令变量flag置为1。如果在一趟过程中都没有数比后面的数更大了，变量flag不作任何修改仍然为0，说明数组已经有序。
最后我们在每一趟结束后判断变量flag是否为0；如果flag为1，说明数组还没有排序好，程序仍然继续下一趟排序；如果flag为0，说明数组已经排序好了，不进行下一趟排序，退出。从而达到减少趟数的效果。
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//对外循环进行优化1
void BubbleSort1(int* p, int sz)
{
int i = 0;
int j = 0;
for (i = 0; i < sz - 1; i++) // 控制趟数
{
//变量flag一定要放在每一趟的开头，这样flag每一趟才会置为0
int flag = 0;
for (j = 0; j < sz - 1 - i; j++) //控制每一趟比较的次数
{
if (p[j] > p[j + 1])
{
//发现前面的数比后面的数大，数组没有序
//把flag置为1
int tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
flag = 1;
}
}
// 在每一趟结束后判断flag是否改变
if (flag == 0)
{
//flag没有变，数组已经有序，退出排序即可
return;
}
}
}
void Print(int* p, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", p[i]);
}
printf("\n");
}
int main()
{
//用两个数组来验证
int arr[] = { 5,6,1,3,4,2,7,8 };
int arr2[] = { 10,9,8,7,6,5,4,3,2,1 };
//求出数组内的元素个数为sz
int sz = sizeof(arr) / sizeof(arr[0]);
int sz2 = sizeof(arr2) / sizeof(arr2[0]);
//排序数组arr
BubbleSort1(arr, sz); //优化版本1的冒泡排序
Print(arr, sz); //打印函数
//排序数组arr2
BubbleSort1(arr2, sz2);
Print(arr, sz);
return 0;
}
对内循环进行优化
大家再来看看原来数组排序的过程：
大家发现一个问题没有，那就是在排序过程中后面一小段本来已经是有序的了，不需要我们再进行排序，我们只需要排序到最后元素交换的地方就可以了。
思路如下：
我们设个变量max来记录，最后一次元素交换的下标，从而我们在下一趟的排序中，只需要排序到变量max的地方即可，并且加上上面分析的趟数优化即可。
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void BubbleSort2(int* p, int sz)
{
int i = 0, j = 0;
int pos = sz - 1; //第一次排序的极限先给到最后一个元素
int max = 0; //来保存最后一次交换的下标
for (i = 0; i < sz - 1; i++)
{
int flag = 0;
for (j = 0; j < pos; j++)
{
if (p[j] > p[j + 1])
{
int tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
flag = 1;
//每一次交换都把下标保存到max中
max = j;
//不能在这里直接把j赋值给pos，
//这里不能确定是最后一次元素交换的下标
//要等到每一趟结束后才行
}
}
// 每一趟过后把保存的下标赋值给pos
//这里也不能直接把j赋值给pos，
//因为最后一次交换的下标j还会继续变化
pos = max;
if (flag == 0)
{
//flag没有变，数组已经有序，退出排序即可
return;
}
}
}
void Print(int* p, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", p[i]);
}
printf("\n");
}
int main()
{
//用两个数组来验证
int arr[] = { 5,6,1,3,4,2,7,8 };
int arr2[] = { 10,9,8,7,6,5,4,3,2,1 };
//求出数组内的元素个数为sz
int sz = sizeof(arr) / sizeof(arr[0]);
int sz2 = sizeof(arr2) / sizeof(arr2[0]);
//排序数组arr
BubbleSort2(arr, sz); //优化版本2的冒泡排序
Print(arr, sz); //打印函数
//排序数组arr2
BubbleSort2(arr2, sz2);
Print(arr, sz);
return 0;
}
双向冒泡排序
我们在排序的过程中有时候会碰到特殊的例子，比如排序：9 1 2 3 4 5 6 0 。最大数9在最左边，而最小数0却在最右变，如果还是按照上面的方法优化是节省不了多少步数的。我们还需要另外一种方法才行。
思路如下：
这时候我们会想如果把最大数9和最小数0调换位置不就可以了嘛，所以我们想到了既然数组可以从左向右遍历，那也可以从右往左遍历。从左向右把最大的数移到最右；从右往左把最小的数移到最左。我们设两个变量left和right，当left小于right排序才执行，不然就退出。然后再加上前面的两种优化退出方式。
图片分析如下：
代码如下：
//最终版本优化
void BubbleSort3(int* p, int sz)
{
int left = 0; //左边起始下标为0
int right = sz - 1; //右边起始下标为最后一个元素
int max = 0;
int min = 0;
while (left < right)
{
int i = 0;
int flag = 0;
// 从左边到右边排序
for (i = left; i < right; i++)
{
if (p[i] > p[i + 1])
{
int tmp = p[i];
p[i] = p[i + 1];
p[i + 1] = tmp;
flag = 1;
// 保存交换的下标
max = i;
}
}
//把最后交换的下标赋值给right
right = max;
if (flag == 0)
{
return ;
}
// 从右边往左边排序
flag = 0; //要把flag重新置为0
for (i = right; i > left; i--)
{
if (p[i] < p[i - 1])
{
int tmp = p[i];
p[i] = p[i - 1];
p[i - 1] = tmp;
flag = 1;
min = i;
}
}
//把最后交换的下标赋值给right
left = min;
if (flag == 0)
{
return ;
}
}
}
qsort函数
大家发现没有，前面分析的冒泡排序只能对整数进行排序，当我们想对字符串或者字符类型排序时就实现不了，那么有什么方法来解决呢？
我们就得提起qsort函数了，它能够对任何类型进行排序，下面是它的用法与解析。
分析与使用
值得注意的是最后一个参数是函数指针类型，它要我们写一个函数来实现比较两个元素，然后qsort函数会自动帮我们进行排序。
使用举例：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//比较整形类型大小的函数
int compar1(const void* a, const void* b)
{
if ((*(int*)a - *(int*)b) > 0)
{
return 1;
}
else if ((*(int*)a - *(int*)b) == 0)
{
return 0;
}
else
{
return -1;
}
//return ( *(int*)a - *(int*)b );
//这样有可能会产生溢出
}
//比较字符类型大小的函数
int compar2(const void* a, const void* b)
{
if ((*(char*)a - *(char*)b) > 0)
{
return 1;
}
else if ((*(char*)a - *(char*)b) == 0)
{
return 0;
}
else
{
return -1;
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1 };
char arr2[] = "gfedcba";
int sz = sizeof(arr) / sizeof(arr[0]);
int sz2 = strlen(arr2);
//对整形类型进行排序
qsort(arr, sz, sizeof(arr[0]), compar1);
//对字符类型进行排序
qsort(arr2, sz2, sizeof(arr2[0]), compar2);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("%s\n", arr2);
return 0;
}
程序执行结果如下：
模拟实现qsort函数
经过上面的举例使用我们大概了解qsort函数的特性，那么再结合我们前面所分析的冒泡排序，我们能不能使用冒泡排序来模拟实现qsort函数呢？
分析如下：
我们实现这个函数有两个难点：第一是怎么找到我的下一位元素呢？因为数组的第一个元素指针是void* 类型的，从而加减的步伐大小就不能确定。
第二个难点，就算确定两个元素了，因为数组的第一个元素指针是void* 类型的，就不能进行解引用，从而就不能进行元素之间进行交换了。
那么有没有解决的办法呢？
我们再来看看qsort函数的四个参数，其中第三个参数比较有特点，要把数组中的元素大小传过去，这有什么用处呢？这个参数是实现qsort函数的关键。
我们知道在所有指针类型当中，char* 类型指针的步伐是最小的，每次加一就跳过一个字节，所以当我们知道元素的大小即宽度之后，我们把第一个元素指针是void* 强制转化为char* 类型，在循环体中用个变量j乘上宽度再加上第一个元素指针，这样可以随便找到数组中的任意元素。
而我们知道元素的宽度，在两个元素交换的时候我们可以一个字节一个字节的交换，交换的次数就是元素的宽度。这样两个难点就解决了。
代码实现如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct people
{
char name[10];
int age;
char fun[10];
double grade;
};
//比较整形类型大小的函数
int compar1(const void* a, const void* b)
{
if (((struct people*)a)->age - ((struct people*)b)->age > 0)
{
return 1;
}
else if (((struct people*)a)->age - ((struct people*)b)->age == 0)
{
return 0;
}
else
{
return -1;
}
}
int compar3(const void* a, const void* b)
{
return strcmp(((struct people*)a)->name, ((struct people*)b)->name);
}
void Swap(char* str1, char* str2, int width)
{
//交换元素，一个字节一个字节进行交换
//交换的次数为宽度大小
while (width--)
{
char tmp = *(str1);
*(str1) = *(str2);
*(str2) = tmp;
str1++;
str2++;
}
}
void my_qsort(void* base, int sz, int width, int compar(const void* a, const void* b))
{
//冒泡排序的方式实现qsort
int i = 0, j = 0;
for (i = 0; i < sz - 1; i++)
{
int flag = 0;
for (j = 0; j < sz - 1 - i; j++)
{
//把要比较的元素地址传给比较函数compar
if (compar((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交换元素
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
flag = 1;
}
}
if (flag == 0)
{
return;
}
}
}
void Print(struct people* pc,int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s ", pc[i].name);
printf("%d ", pc[i].age);
printf("%s ", pc[i].fun);
printf("%f ", pc[i].grade);
printf(" ");
}
printf("\n\n");
}
int main()
{
struct people arr[] =
{ {"zhangsan",22,"add",3.14},{"lisi",18,"sub",6.67},{"wangw",28,"ghe",8.84} };
int sz = sizeof(arr) / sizeof(arr[0]);
//对字符串大小进行排序
printf("对字符串大小进行排序:\n");
my_qsort(arr, sz, sizeof(arr[0]), compar3);
Print(arr, sz);
// 对整形大小进行排序
printf("对整形大小进行排序:\n");
my_qsort(arr, sz, sizeof(arr[0]), compar1);
Print(arr, sz);
return 0;
}
注意：qsort函数可以帮我们实现很多类型的排序，但是我们要自己写一个能比较两个元素大小的函数，并且把函数地址传给qsort。
程序执行结果：
