冒泡排序：将一个无序数组排序成有序数组(升序/降序)
时间复杂度O(n²)
空间复杂度O(1)
int nums[] = { 3,5,7,1,2,8,9,4,6,10 };
首先随机初始化一个无序数组 这里统一将它调整为升序（降序同理）
int main()
{
int nums[] = { 3,5,7,1,2,8,9,4,6,10 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int i = 0;
for (i = 0; i < numsSize; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
bubble_sort(nums,numsSize);
for (i = 0; i < numsSize; i++)
{
printf("%d ", nums[i]);
}
return 0;}
在冒泡排序前后分别打印一次数组 ，对比冒泡排序前后数组的变化。
接下来定义冒泡排序函数主体
void bubble_sort(int* nums,int numsSize)
{
int i = 0;
for (i = 0; i < numsSize - 1; i++)//确定冒泡排序趟数
{
//定义每一趟冒泡排序具体内容
int j = 0;
int flag = 1;//假设这趟冒泡排序已经有序
for (j = 0; j < numsSize - 1 - i; j++)//两两比较次数为numsSize-1-i次
{
if (nums[j] > nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = 0;
}
}
if (flag == 1)//如果flag == 1 说明此时数组已经有序
break;
}}
其实冒泡排序的核心内容就是交换两个变量的值
参考基于交换变量的值的研究_lovepotato_的博客-CSDN博客
这里来讲一讲如何减少两两比较的次数
目录
1.首先要确定冒泡排序的趟数
2.定义一趟冒泡排序的具体内容
3.减少比较次数
1.首先要确定冒泡排序的趟数
趟数最多是 (数组元素个数 - 1) 次。为什么是最多呢
这里假设一个数组是完全倒序的 把它排成升序(例如如下这个数组)
int nums[] = { 9,8,7,6,5,4,3,2,1 };
从i = 0 开始 第一趟冒泡排序的实际上就是把 9 一直移动到最后 其余元素相对顺序不变
int nums[] = { 8,7,6,5,4,3,2,1,9 };
同理 第二趟冒泡排序把 8 移动到倒数第二个位置 依次类推
排到最后会发现 最后两个元素(1和2)的顺序是一趟冒泡排序中排好的，所以次数是numsSize - 1次
这就是次数最多的情况。
2.定义一趟冒泡排序的具体内容
//定义每一趟冒泡排序具体内容
int j = 0;
int flag = 1;//假设这趟冒泡排序已经有序
for (j = 0; j < numsSize - 1 - i; j++)//两两比较次数为numsSize-1-i次
{
if (nums[j] > nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = 0;
}
}
if (flag == 1)//如果flag == 1 说明此时数组已经有序
break;
这里有个小坑 内存for循环的循环次数是numsSize-1-i次
for (j = 0; j < numsSize - 1 - i; j++)
理由：i=0 当第一趟冒泡排序排好之后 i++变成1 ，此时最后一个元素已经定好了最终位置，只需要剩下的前8个元素进行冒泡排序即可，下标最大为numsSize -1 -i
3.减少比较次数
这里为什么要再定义一个flag变量呢？
为了减少两两比较的次数，优化算法。
在每一趟冒泡排序开始之前 初始化flag = 1 用来假设此趟冒泡排序之前数组已经有序
为什么要这样做呢？随机的数组不一定都是无序的 有可能只是其中某几个元素需要交换
例如下面这个数组
int nums[] = { 1,2,3,4,6,5,7,8,9 };
这个数组其实只需要5和6交换位置就有序了
但如果没有flag变量的话 计算机就需要从头比较到尾 每两个元素都比较一下，看看是否要交换
重复性高。
flag具体实现：
if (nums[j] > nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = 0;
}在if语句中定义flag的值为0，一趟冒泡排序中，但凡两个元素需要交换，就会进入这个if语句
把flag重新定义为0。
if (flag == 1)//如果flag == 1 说明此时数组已经有序
break;如果没有进入if语句，flag仍然为1，说明此时数组已经有序了(没有任何两个元素需要交换)，然后立马break跳出 ，后面的循环就不再进行了
这就很好的减少了重复比较的问题。
整体代码实现：
c语言：
void bubble_sort(int* nums,int numsSize)
{
int i = 0;
for (i = 0; i < numsSize - 1; i++)//确定冒泡排序趟数
{
//定义每一趟冒泡排序具体内容
int j = 0;
int flag = 1;//假设这趟冒泡排序已经有序
for (j = 0; j < numsSize - 1 - i; j++)//两两比较次数为numsSize-1-i次
{
if (nums[j] > nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = 0;
}
}
if (flag == 1)//如果flag == 1 说明此时数组已经有序
break;
}}
int main()
{
int nums[] = { 3,5,7,1,2,8,9,4,6,10 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int i = 0;
for (i = 0; i < numsSize; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
bubble_sort(nums,numsSize);
for (i = 0; i < numsSize; i++)
{
printf("%d ", nums[i]);
}
return 0;}
Java:
public class Test {
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
boolean flag = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
flag = false;
}
}
if(flag == true){
return;
}
}
}
public static void main(String[] args) {
int[] arr = {3,1,2,5,7,9,6,10};
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
打印的结果如下：
但是冒泡排序函数有一个局限：只能排序整型类型的数组
但有时候需要比较浮点型数组，结构体数组，冒泡排序函数就无法继续使用
能不能拓展到任意类型呢？ 答案肯定是有的。
这里类比qsort函数来实现bubble_sort函数的拓展形式
void bubble_sort(void base,int sz,int width,int (cmp)(void e1,voide2))
1.第一个参数：待排序数组的首元素地址
2.第二个参数：待排序数组的元素个数
3.第三个参数：待排序数组的每个元素的大小，单位是字节
4.第四个参数：函数指针，比较两个元素所用函数的地址 - (这个函数是使用者自己实现的)
这个函数指针的两个参数：待比较的两个元素的地址
解释：
1.第一个参数void base，因为未知待排序数组的类型，使用void类型的指针可以接收任意类型的数组名。
2.第四个参数cmp，是一个函数指针，由于每一种类型的数组元素不同，所使用的比较函数也不同
bubble_sort函数主体定义:
void bubble_sort(void base,int sz,int width,int cmp(const void e1,const void* e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
int flag = 1;
for (j = 0; j < sz - 1 - i; j++)
{
if ( cmp( (char*)base+j*width, (char*)base+(j+1)*width ) > 0 ) // > 0说明 第一个参数大于第二个 说明需要交换
{
//交换
swap( (char*)base + j * width, (char*)base + (j + 1) * width , width );
flag = 0;
}
}
if (flag == 1)
break;
}}
函数的整体框架与原来的冒泡排序函数一样，唯二变的是内层for循环中的 if判断条件和交换的内容
比较函数cmp的定义是：
cmp(char e1,char e2)
若 e1 > e2 则返回 > 0的数字
e1 = e2 则返回0
e1 < e2 则返回 < 0的数字
这里固定将待排序数组调整为升序，所以当比较函数cmp的返回值 > 0才进行交换
注意点：
为什么这里要把base(待交换的元素地址)强制类型转化为char*呢
解决这个问题首先要了解一个概念：
指针的类型决定了+/-整数向后/向前访问的字节数
char*类型每次访问1个字节
int*类型每次访问4个字节
size*类型每次访问size大小的字节
由于未知待排序数组的类型，不同类型的地址每次访问的时候对应不同的字节数，这里将base强制类型转化为char，每次固定只能访问一个字节，charbase+j*width等价于向后访问了width个字节，也就解决了指针访问步长的问题，排序的时候只需要将width赋值为相同类型的字节数即可。
例如：排序整型数组，就把width赋值为sizeof(int)，也就是4
接下来就定义swap函数：
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++;
}}
buf1和buf2为待交换的两个元素的首字节地址，由于未知类型，这里需要在传一个width，以便直到具体需要交换几个字节。
这样函数的主体部分就实现完了。
接下来依次排序一下整型，浮点型，结构体类型的数组
目录
1.整型：
2.浮点型：
3.结构体类型
1.整型：
定义数组：
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
定义比较函数：
int int_cmp(const void e1,const void e2)
{
return *(int*)e1 - *(int*)e2;//整数 可以直接 > < = 比较}
由于比较类型是整型，整型是可以直接 > < = 比较的，
void类型的指针是无法+/-访问字节的，先把e1,e2强制类型转化为int，然后直接return相减的结果就行了。
函数传参：
bubble_sort(arr, sz, sizeof(int), int_cmp);
调试看效果：
2.浮点型：
同整型数组一样
定义数组：
float arr2[] = { 9.0,8.0,7.0,6.0,5.0 };
int sz2 = sizeof(arr2) / sizeof(arr2[0]);
比较函数：
int float_cmp(const void e1,const voide2)
{
if (*(float*)e1 - *(float*)e2 > 0)
{
return 1;
}
else
return 0;}
比较函数这里有个小注意点：
比较函数cmp的参数固定为int，(float)e1 - (float)e2 为两个浮点数相减，结果还是浮点型，
直接return (float)e1 - (float)e2 会报警告，float 到 int的不兼容 可能会丢失数据，这里为了避免
警告使用if语句判断，如果差值大于0就返回1，否则返回0，这样不仅避免了警告，同时也满足差
值>0就返回>0的数字的设定。
函数传参：
bubble_sort(arr2,sz2,sizeof(float),float_cmp);
调试看结果：
3.结构体类型
同上面一样
定义结构体数组：
struct Stu
{
char name[20];
int age;};
struct Stu s[3] = { {"zhangsan",20}, {"lisi",30}, {"wangwu",10}};
int sz3 = sizeof(s) / sizeof(s[0]);
这里分别将数组中的name和age排序:
(1)age：
比较函数：
int Stu_by_age(const void e1, const void e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}
由于是结构体指针，需要使用 -> ——结构体成员访问操作符
age也是整型，所以这里同样是return它们的差值即可
调试看效果：
最后成功按照年龄升序排序
(2)name：
比较函数：
int Stu_by_name(const void e1, const void e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);}
由于name是字符串，这里需要用到字符串比较函数 strcmp
strcmp函数的返回类型与cmp刚好一致：
所以可以直接return strcmp函数的返回值
调试看效果：
整体代码实现：
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 e1,const void* e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
int flag = 1;
for (j = 0; j < sz - 1 - i; j++)
{
if ( cmp( (char*)base+j*width, (char*)base+(j+1)*width ) > 0 ) // > 0说明 第一个参数大于第二个 说明需要交换
{
//交换
swap( (char*)base + j * width, (char*)base + (j + 1) * width , width );
flag = 0;
}
}
if (flag == 1)
break;
}}
int int_cmp(const void e1,const void e2)
{
return *(int*)e1 - *(int*)e2;//整数 可以直接 > < = 比较}
int float_cmp(const void e1,const voide2)
{
if (*(float*)e1 - *(float*)e2 > 0)
{
return 1;
}
else
return 0;}
struct Stu
{
char name[20];
int age;};
int Stu_by_age(const void e1, const void e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}
int Stu_by_name(const void e1, const void e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
float arr2[] = { 9.0,8.0,7.0,6.0,5.0 };
int sz2 = sizeof(arr2) / sizeof(arr2[0]);
struct Stu s[3] = { {"zhangsan",20}, {"lisi",30}, {"wangwu",10}};
int sz3 = sizeof(s) / sizeof(s[0]);
bubble_sort(arr, sz, sizeof(int), int_cmp);
bubble_sort(s, sz3, sizeof(s[0]), Stu_by_age);
bubble_sort(s, sz3, sizeof(s[0]), Stu_by_name);
bubble_sort(arr2,sz2,sizeof(float),float_cmp);
return 0;}
