目录
1.冒泡排序的定义
2.冒泡排序的原理
3.代码及其解析
4.冒泡排序的改进
5.实现冒泡排序函数
生命中永远会有令人懊恼的事,但我知道,我们是为了不留遗憾活着的,对吗?
1.冒泡排序的定义
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端,但是在广泛适用后,冒泡排序可以用来排任意顺序。
2.冒泡排序的原理
假设要将已知无需数列按从小到大排列,将第一个元素与后面的元素依次比较,如果必后面的元素小,就与后面某个元素交换位置,然后用这个元素再依次往后比较,遇到比这个元素小的就与这个元素交换,直到最后一个元素,就完成了一趟冒泡排序,则最后一个元素一定是这个序列里最大的一个元素;然后开始第二趟冒泡排序,继续从第一个元素开始往后一次比较,遇到较小的就交换位置,直到倒数第二个数,那么最后倒数第二个数就变成了第二大的数.......依次排完序列中所有的数,那么这个数的顺序就会变成从小到大,下面我用图来演示
第一趟冒泡排序,是对序列中所有数进行操作
第 i 趟冒泡排序,是对序列中除最后一个数外(10-i)个数进行操作
3.代码及其解析
#include<stdio.h>
int main()
{
int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
int i = 0;
printf("排序前的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
printf("排序后的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
运行结果:
代码解析:外部循环控制冒泡排序的趟数,for循环从0开始,循环sz-1(数组元素-1)次,内部循环控制每次具体的冒泡排序过程,因为每趟冒泡排序需要进行比较的次数递减,所以在循环的控制条件那再减去i来控制每趟冒泡排序进行的比较次数。在内部循环的循环体内,对这趟冒泡排序需要排序的元素进行遍历,小的元素放前面,大的逐次往后走,没趟冒泡结束后都能确定一个元素的位置。(sz-1)趟冒泡排序结束后,冒泡排序及就结束了。当然,如果想进行从大到小排序,只需要改变冒泡排序的判断部分,将大的元素放前面,小的元素往后走即可,代码如下:
#include<stdio.h>
int main()
{
int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
int i = 0;
printf("排序前的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] < arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
printf("排序后的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
运行结果:
4.冒泡排序的改进
由于冒泡排序的时间复杂度实在太高,所以冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。
#include<stdio.h>
int main()
{
int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
int i = 0;
printf("排序前的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
int flag = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] >arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag++;
}
}
if(flag==0)
break;
}
printf("排序后的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
方法就是在每次冒泡后,检验一下到底这趟冒泡排序有没有交换顺序,如果没有的话,那么flag的值没有发生变化,就可以直接退出循环,这种方法可以略微提升一下效率。
5.实现冒泡排序函数
用函数实现冒泡排序,传参方法跟数组传参相同,具体可参考C语言函数详解
里面有具体介绍数组传参的方法,这里就直接上代码
#include<stdio.h>
void Bubble_Sort(int arr[], int sz)
{
int flag = 0;
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag++;
}
}
if (flag == 0)
break;
}
}
int main()
{
int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
int i = 0;
printf("排序前的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
Bubble_Sort(arr, sz);
printf("排序后的数组:");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
文章来源:https://www.toymoban.com/news/detail-513044.html
本文收录于基础算法 、C语言学习专题 、水火莲花-C疑难专题文章来源地址https://www.toymoban.com/news/detail-513044.html
到了这里,关于冒泡排序(超详细图解加代码解析,5分钟看懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!