冒泡算法

2015-08-14 20:30 阅读 3,424 次 评论 0 条
版权声明:本文著作权归TeachCourse所有,未经许可禁止转载,谢谢支持!
转载请注明出处:http://teachcourse.cn/326.html

一.摘要

什么是冒泡排序算法,如何使用冒泡排序算法?基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

二.封装

将一个数组的元素两两比较,将大的元素交换位置并逐渐“上浮”到右边

定义一个需要排序的数组:int num[]={4,6,2,5,8,9}


第一趟:找到数组{4,6,2,5,8,9}最大的元素并“上浮”到右边

指针位置为0,4和6比较,4小于6,不需要交换位置

无序数组,:{4,6,2,5,8,9}

指针位置为1,6和2比较,6大于2,交换位置

无序数组:{4,[2],[6],5,8,9}

指针位置为2:6和5比较,6大于5,交换位置

无序数组:{4,2,[5],[6],8,9}

指针位置为3,6和8比较,6小于8,不需要交换位置

无序数组:{4,2,5,6,8,9}

指针位置为4,8和9比较,8小于9,不需要交换位置

无序数组:{4,2,5,6,8,9}


第二趟:找到数组{4,2,5,6,8,9}最大的元素并“上浮”到右边

指针位置为0,4和2比较,4大于2,交换位置

无序数组:{[2],[4],5,6,8,9}

指针位置为1,4和5比较,4小于5,不需要交换位置

无序数组:{2,4,5,6,8,9}

指针位置为2,5和6比较,5小于6,不需要交换位置

无序数组:{2,4,5,6,8,9}

指针位置为3,6和8比较,6小于8,不需要交换位置

无序数组:{2,4,5,6,8,9}

指针位置为4,8和9比较,8小于9,不需要交换位置

无序数组:{2,4,5,6,8,9}


同理,程序依次执行

第三趟...

第四趟...

第五趟...


对于一个长度为N的数组,需要执行(N-1)趟,每一趟需要比较次数分别为:N-1,N-2,N-3...3,2,1

C表示比较次数,用M表示移动次数

最坏的时间复杂度:一个逆序的数组

$C_{max}=\frac{[(n-1)+1](n-1)}2=\frac{n(n-1)}2=O(n^2)$

$M_{max}=\frac{3[(n-1)+1](n-1)}2=\frac{3n(n-1)}2=O(n^2)$

    int num[] = { 4, 6, 2, 5, 8, 9 };

    for (int i = 0; i < num.length-1; i++) {
        int tmp;// 临时变量
        for (int j = 0; j < num.length-1; j++) {
            if (num[j] > num[j + 1]) {
                tmp = num[j];
                num[j] = num[j + 1];
                num[j + 1] = tmp;
            }
        }
    }

    for (int i = 0; i < num.length; i++) {
        System.out.println("num[" + i + "]=" + num[i]);
    }

百度百科:冒泡排序

Java中的经典算法之冒泡排序(Bubble Sort)

关注公众号 扫一扫二维码,加我QQ

如果文章对你有帮助,欢迎点击上方按钮关注作者

来源:TeachCourse每周一次,深入学习Android教程,关注(QQ1589359239或公众号TeachCourse)
转载请注明出处:http://teachcourse.cn/326.html
Android开发之深入理解RectF和Rect之间的区别 Android开发之深入理解RectF和
浅谈mysql存储引擎 浅谈mysql存储引擎
Android事件分发流程分析证明(1) Android事件分发流程分析证明(
详细了解WebChromeClient源码各方法使用说明 详细了解WebChromeClient源码

发表评论

呲牙 憨笑 坏笑 偷笑 色 微笑 抓狂 睡觉 酷 流汗 鼓掌 大哭 可怜 疑问 晕 惊讶 得意 尴尬 发怒 奋斗 衰 骷髅 啤酒 吃饭 礼物 强 弱 握手 OK NO 勾引 拳头 差劲 爱你

表情