网站app建设图片,织梦网站登录,凡科网网站建设,南宁的网站建设#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前正在学习c和算法 ✈️专栏#xff1a;数据结构 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助… 个人主页Weraphael ✍作者简介目前正在学习c和算法 ✈️专栏数据结构 希望大家多多支持咱一起进步 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 目录 一、算法思想二、算法分析三、代码实现四、优化版思路 代码实现五、性能分析 一、算法思想 算法思想两两相邻的元素进行比较不满足要求则交换。
二、算法分析
为了加深对冒泡排序的理解我们先模拟过程以升序为例
第一趟排序
第一次排序5和9比较满足升序位置不变 5,9,3,6
第二次排序9和3比较不满足升序位置交换5,3,9,6
第三次排序9和6比较不满足升序位置交换5,3,6,9此时9已经是最大的无需参与排序
因此第一趟总共进行3次排序。 第二趟排序
第一次排序5和3比较不满足升序位置交换 3,5,6,9
第二次排序5和6比较满足升序位置不变 3,5,6,7此时6已经有序无需参与排序
因此第二趟总共进行2次排序。 第三趟排序
第一次排序3和5比较位置不变 3,5,6,7已经有序
因此第三趟总共进行1次排序。
【总结】
通过以上过程的模拟我们可以总结以下规律
3个数进行冒泡排序总趟数为3那么n个数进行冒泡排序总趟数为n - 13个数进行冒泡排序第一个数内部排序的次数为3第二个数内部排序的次数为2…那么n个数进行冒泡排序内部的趟数应该是n - 1 - i
三、代码实现
#include stdio.hvoid Swap(int* p1, int* p2)
{int t *p1;*p1 *p2;*p2 t;
}void bubble_sort(int* a, int n)
{// n个数有n - 1躺for (int i 0; i n - 1; i){// 1个数需要排n - 1 - i次for (int j 0; j n - 1 - i; j){// 两两比较不满足条件交换if (a[j 1] a[j]){Swap(a[j 1], a[j]);}}}
}int main()
{int a[] { 10,1,6,9,4,7,2,3,8,5 };int aSize sizeof(a) / sizeof(a[0]);bubble_sort(a, aSize);for (int i 0; i aSize; i){printf(%d , a[i]);}printf(\n);return 0;
}【程序结果】 四、优化版思路 代码实现
思路优化版是对序列进行了特判如果某一趟遍历数组发现内部根本没有进行交换就代表其有序
【代码实现】
这里我就不直接给出完整的代码因为我发现有很多人搞不定边界问题这次我就带领大家来一起分析
想搞定任何一个排序问题首先你就必须要先写出单躺 假设i指向序列下标为1的位置那我们就想i最多能到哪个地方(边界)。因为冒泡排序需要进行两两比较那么i就一定不能等于序列长度n。因此i n。以下就是单趟代码
void bubble_sort(int* a, int n)
{// 单趟for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}}
}那接下来想由于单趟排完之后序列的最后一个数已经是有序的了那么循环的判断条件就不能一直是i n必须要有一个变量来控制。而一开始我我们已经分析过了n个数的冒泡排序的总趟数是n - 1
void bubble_sort(int* a, int n)
{for (int j 0; j n - 1; j){for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}}}
}最后再根据优化思路因此优化后的完整代码 如下
【完整代码】
#include stdio.h
#include stdbool.hvoid Swap(int* p1, int* p2)
{int t *p1;*p1 *p2;*p2 t;
}void bubble_sort(int* a, int n)
{for (int j 0; j n - 1; j){bool flag true;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);flag false;}}// 如果一趟排序后没有发生交换-flag没有发生改变// 那么序列一定有序if (flag)break;}
}int main()
{int a[] { 10,1,6,9,4,7,2,3,8,5 };int aSize sizeof(a) / sizeof(a[0]);bubble_sort(a, aSize);for (int i 0; i aSize; i){printf(%d , a[i]);}printf(\n);return 0;
}五、性能分析
时间复杂度
① 未优化版的时间复杂度最好和最坏的情况不管怎样每一个数都要进行两两比较因此时间复杂度为O(N2 ② 而优化版最好的情况就是第一趟下来没有发生交换因此最好的时间复杂度是O(N)最坏的情况还是O(N2
综上冒泡排序的时间复杂度是O(N2
空间复杂度O(1)稳定性稳定
