活动地址:CSDN21天学习挑战赛
✅作者简介:C/C++领域新星创作者,为C++和java奋斗中
✨个人社区:微凉秋意社区
🔥系列专栏:经典算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题
🔥前言
今天总结一下优化版的经典算法——冒泡排序,不同于以往的暴力二重for循环,这里的冒泡排序增加了一个标志位。我们要理解该冒泡排序的概念,算法流程与算法思想,探讨时间复杂度。这也是本专栏第六篇博文,感兴趣的朋友可以订阅以便持续观看。
文章目录
- 冒泡排序算法解析
-
- 一、理解冒泡排序思想
-
- 1、算法概念
- 2、算法思想
- 二、算法分析
-
- 1、算法流程
- 2、实现步骤
- 三、代码实现
-
- 1、源码及运行效果
- 2、时间复杂度分析
冒泡排序算法解析
一、理解冒泡排序思想
1、算法概念
也称气泡排序,是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较,将不满足相对顺序的一对儿元素进行交换,再进行下一对元素的比较。
2、算法思想
总结来说,每一趟冒泡排序将会排好一个元素(极值)。不断的在无序区中执行该步骤,如果在某一次比较的过程中没有发生元素的交换,则证明元素都已经有序,可以提前结束整个算法。或者直到无序区中的元素减少到一个时,整个算法结束,此时整个序列有序。
二、算法分析
1、算法流程
假如要对该序列进行冒泡排序,解析一下算法流程:
- 第一趟排序:7和4 交换位置,变为:
- 第二趟排序:6和4 交换位置,变为:
- 此时序列符合升序排列,提前结束循环,排序完成,退出循环
2、实现步骤
- 首先当外层循环 i 为0时,内层循环中从序列里第一个元素开始两两计较,不是升序则交换位置,是升序则往后遍历,那么第一次外层循环一定可以确定最大值且位置在序列末尾。
- 那么当外层循环次数增多,内层循环范围就要对应缩减,应为总长度 - 外层循环次数 - 1(减1是为了防止 i 等于0时数组溢出)。
- 重复以上步骤,如果序列已经为升序,通过标志位来提前结束程序。
三、代码实现
1、源码及运行效果
C++源代码:
#include<iostream>
using namespace std;
//冒泡排序声明
void maopaosort(int A[], int len);
//冒泡排序实现
void maopaosort(int A[], int len)
{
for (int i = 0; i < len; i++) {
int flag = 0;//标志位
for (int j = i; j < len - i - 1; j++) {
if (A[j] > A[j + 1]) {
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
flag = 1;
}
}
if (flag == 0)//如果已经升序,不再继续外层循环,结束此函数
return;
}
return ;
}
int main(void)
{
int A[7] = { 3,6,7,4,8,9,10 };
int len = sizeof(A) / sizeof(A[0]);
cout << "排序前:" << endl;
for (int i = 0; i < len; i++) {
cout << A[i] << " ";
}
maopaosort(A,len);
cout << "排序后:" << endl;
for (int i = 0; i < len; i++) {
cout << A[i] << " ";
}
}
运行效果:
2、时间复杂度分析
- 最好的情况:
- 该序列为升序排列,内层循环执行了
n-1
次,那么相当于遍历了n次,时间复杂度为O(n)。
- 该序列为升序排列,内层循环执行了
- 最坏的情况:
- 对于冒泡排序来说,最坏的情况依然是元素逆向有序,此时需要执行n-1趟,并且两两元素都需要交换,相当于是最小的元素排在末尾,—路交换到第一位,然后是次最小一路交换至第二位,此时的时间复杂度为: O(
n
2
n^2
- 对于冒泡排序来说,最坏的情况依然是元素逆向有序,此时需要执行n-1趟,并且两两元素都需要交换,相当于是最小的元素排在末尾,—路交换到第一位,然后是次最小一路交换至第二位,此时的时间复杂度为: O(
- 平均情况:
- 综合考虑下,冒泡排序算法的时间复杂度为O(
n
2
n^2
- 综合考虑下,冒泡排序算法的时间复杂度为O(
那么有关优化版冒泡排序算法的分析到此结束了,快去敲一波代码试试效果吧!最后期待你的关注与支持,让我们共同进步!
相关文章
暂无评论...