top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

排序算法:交换排序之冒泡排序
利用交换数据元素的位置进行排序的方法称作交换排序。常用的交换排序方法有冒泡排序和快速排序。

冒泡排序不用多说,其本身的名称也很适合这个算法的描述。每次循环都将未处理的元素中最大(或最小)的元素移到未处理元素的末端,或者说排列数据的开端,随便怎么说。这个算法和直接选择排序有相同的地方,都是每次寻找未处理元素集中的最大(或最小)元素,然后再处理已排列元素集。不同的是二者对于已经找到的元素的处理方式(或者说查找符合条件的元素的方式不同),即交换和插入的区别,这个也是最主要区别, 另外,冒泡排序是稳定的排序算法

C语言实现及测试:
#include <stdio.h>

/**
 * 冒泡排序:升序
 * @param data 待排序集合
 * @param len  集合长度
 *
 * 注: 此处为方便演示,依旧只是进行简单的 int数组 排序
 */
void bubbleSortAsc(int data[], int len){

    int i = 0, j = 0, flag = 1, temp = 0;

    //进行一次循环之后如果未发生任何数据变动, 即 flag=0 则表示当前集合已经是有序的,结束循环
    for(i = 1; i < len && flag == 1; i++){
        flag = 0;
        for(j = 0; j < len-i; j++){
            if(data[j] > data[j+1]){
                flag = 1;
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
}

int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23};
    int n = 12;
    bubbleSortAsc(a, n);

    for(i = 0; i < n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}


分析
冒泡排序算法最好的情况是数据集合已经按需求排好序,这时,只需执行一次内循环算法就跑完了,也就是内循环 n-1 次, 所以冒泡排序算法最好的情况是时间复杂度为 O(n);

冒泡排序最坏的情况是数据集合逆序存放,这样,外层循环 n-1 次,结合内层循环,有:
比较次数:n(n-1)/2
移动次数:3n(n-1)/2
所以冒泡排序算法最坏的情况时间复杂度为 O(n2)

冒泡排序空间复杂度同直接插入排序一致:O(1)。并且冒泡排序是一种稳定的排序算法。

总结
冒泡排序是最基础的排序算法,记得老师讲的第一个排序算法就是冒泡排序,虽然基础,还是有必要总结一下。以上只是个人看法,若您有不同看法,欢迎留言评论。您还可以在本站查看系列文章, 点击相应标签即可。

【原创内容,转载请注明出处】
标签
排序
算法
交换排序
冒泡排序
BubbleSort
上一篇:排序算法:选择排序之直接选择排序
下一篇:排序算法:交换排序之快速排序
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
分享

关于友情链接

友情链接申请请到留言板块留言。注明网站名称及网址。期待您的友链,欢迎留言。
最新留言
[2018/04/07]太难找了,找到了
[2018/03/20]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/20] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/19]你加我友链了????
[2017/11/19]你的alert 很不友好哈
[2017/11/19]友链已添加
[2017/11/19]路过帮踩。
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3