社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
英文名:Bubble Sort
是一种简单的排序算法
由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
以下用数组2,5,8,3,6,9,1,4,7为例
从小到大排序
首先是2和5,符合,过
然后5和8,也没有问题
- 接着8和3就不符合了,所以开始进行处理
后面步骤就不再给出了,可以自己写一下
从以上过程可得,遍历一次就能排序一个数,因此n个数需要n-1次遍历,这就是第一重循环
第二重循环就是遍历所有未排序的数,将最大数交换到最后或最小数交换到最前
假设我们每次从第二个数开始,与前一个数比较
那么第一次我们需要循环的下标就是
- 第二次是
- 最后一次
我们可以发现每次j初始不变,上限减一,因此为了方便我们可以使用i作为j的上限也就是i的值从len-1到1
此外,若数组前几次就已经排完,按上面想法还会循环多次,所以我们使用一个标记来让它排完就结束
#include <iostream>
using namespace std;
void BubbleSort(int a[],int l)
{
int ans;
int temp;
for(int i=l-1;i>=1;i--)//一重循环,n-1次
{
ans=1;
for(int j=1;j<=i;j++)//第二个数到未排序数
{
if(a[j-1]>a[j])
{
ans=0;//有未排序的
// temp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = temp;
swap(a[j],a[j-1]);//交换
for(int k=0;k<l;k++)//打印数组
cout<<a[k]<<" ";
cout<<endl;
}
}
if(ans)//额外标记
break;
}
}
int main()
{
int a[20]={2,5,8,3,6,9,1,4,7};
int b[20] = {1,1,1,1,1,1,1,1,1};
int len=9,temp;
BubbleSort(a,len);
return 0;
}
最好情况就是全部有序,此时只需遍历一次,因此冒泡排序最好的时间复杂度为
O
(
n
)
O(n)
O(n)
最坏情况全部反序,两重for循环全部执行,因此冒泡排序的最坏时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)
综上,因此冒泡排序总的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)
最优的空间复杂度就是不需要借用第三方内存空间,则复杂度为0
最差的空间复杂度就是开始元素逆序排序,每次都要借用一次内存,按照实际的循环次数,为
O
(
n
)
O(n)
O(n)
平均的空间复杂度为: O ( 1 ) O(1) O(1)
相同元素的前后顺序是否改变
因为只交换不同大小的,所以冒泡排序是稳定的
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!