动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

冒泡排序算法详解

06-30 18:01 268浏览
举报 T字号
  • 大字
  • 中字
  • 小字

冒泡排序算法作为我们学习计算机语言的入门排序算法,此时我们即使做不到记忆犹新多多少少也会在脑海中有点印象。冒泡排序,顾名思义,因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。毫不夸张的说,冒泡排序是我们学习排序算法的启蒙老师。

冒泡排序的原理(以递增序为例)是每次从头开始依次比较相邻的两个元素,如果后面一个元素比前一个要大,说明顺序不对,则将它们交换,本次循环完毕之后再次从头开始扫描,直到某次扫描中没有元素交换,说明每个元素都不比它后面的元素大,至此排序完成。冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。如果两个相等的元素相邻,那么根据我们的算法。它们之间没有发生交换;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

时间复杂度是衡量一个算法效率的标准值。我们来计算一下冒泡排序的时间复杂度:

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值:所以,冒泡排序最好的时间复杂度为0(n)

若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值冒泡排序的最坏时间复杂度为0(n²);

综上,冒泡排序总的平均时间复杂度为0(n²)。

实践出真知,我们通过实例来快速掌握冒泡排序的规则和算法:

冒泡排序的算法规则是依次比较相邻的两个数,正序则不动,倒序则交换位置,如此循环,直到整个数组为有序为止。

以下列数据为例:

首先比较索引为0和1的值

3>2,为倒序则进行位置交换

再比较索引为1和2的值3<7,为正序位置不变

再比较索引为2和3的值7>4,为倒序则进行位置交换

再比较索引为3和4的值7>1,为倒序则进行位置交换

此时已经遍历到最后一位(length-1),第一轮位置交换结束

总结:href="">1. 由于是依次比较并交换数值,当前数组中最大的值已经被放到最后的位置

那么接下来的排序则不需要遍历到最后一位,因为最大的1个值已经被排到了最后

第二轮比较

数组中的最大值已经被放到了最后,那么第二轮比较则可以无视最后一位,比较前面的数值(length-1-1)即可

重复第一轮的操作首先比较索引为0和1的值

2<3,为正序位置不变

再比较索引为1和2的值3<4,为正序位置不变

再比较索引为2和3的值4>1,为倒序则进行位置交换

此时已经遍历”7”之前的数(leng-1-1),第二轮结束

第二轮总结:

1. 由于不考虑已经排序好的7,第二轮已经将除最后一位之前(leng-1-1)的数组中最大值交换到了最后位置

2. 那么接下来的排序则不需要遍历到最后2位,因为最大的2个值已经被排到了最后

第三轮比较

数组中的最大值两个值已经被放到了最后,那么第三轮比较则可以无视最后两位,比较前面的数值(leng-1-2)即可重复第一轮的操作首先比较索引为0和1的值

2<3,为正序位置不变

再比较索引为1和2的值3>1,为倒序则进行位置交换

此时已经遍历”4”和”7”之前的数(leng-1-2),第二轮结束

第三轮总结:

1. 由于不考虑已经排序好的4和7,第三轮已经将除最后两位之前(leng-1-2)的数组中最大值交换到了最后位置

2. 那么接下来的排序则不需要遍历到最后3位,因为最大的3个值已经被排到了最后

第四轮比较

数组中的最大值三个值已经被放到了最后,那么第四轮比较则可以无视最后三位,比较前面的数值(leng-1-3)即可重复第一轮的操作首先比较索引为0和1的值

2>1,为倒序则进行位置交换

此时已经遍历”3”和”4”和”7”之前的数(leng-1-3),最后一轮结束

第四轮(最后一轮)总结:

1. 由于不考虑已经排序好的3和4和7,第四轮已经将除最后三位之前(leng-1-3)的数组中最大值交换到了最后位置

2. 此时遍历完毕,数组已经为有序数组

=代码实现==

public class Sort {

    public static void main(String[] args) {

        //示例数据        int arr[] = {3,2,7,4,1};

        System.out.println("====Before====");

        System.out.println(Arrays.toString(arr));

        //进行排序        BubbleSort(arr);

        //展示结果        System.out.println("====After====");

        System.out.println(Arrays.toString(arr));

    }

    //冒泡排序    public static void  BubbleSort(int arr[]){

        int temp;

        for (int i = 0; i < arr.length-1; i++) {

            for (int j = 0; j < arr.length-1-i; j++){

                if (arr[j]>arr[j+1]){

                    temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

            }

        }

    }}

==代码描述==

从第一个位置开始遍历整个数组,使用嵌套循环外层表示排序的次数,有n个数则只需要n-1次即可内层循环则是把当前数值和后一位数值作比较,当前数值比后一位数值大(倒序),则进行交换位置这样一来,内层循环走一遍,则是把当前比较的数组的最大值放到最后位置外层循环走完则是排序完所有数字

冒泡排序作为最基础的经典排序算法,它不仅仅适用于java语言,几乎所有的主流开发语言都能用到它。冒泡排序是我们学习其他排序算法的引路者,也是我们学习计算机算法的基石,我们只有牢牢打下基础,才能在未来的学习发展中没有后顾之忧。

0人推荐
共同学习,写下你的评论
0条评论
十年
程序员十年

13篇文章贡献72369字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消