分类
java 算法

java实现冒泡排序

冒泡排序简介

冒泡排序(英语:Bubble Sort)又称为泡式排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

动图演示

冒泡排序动图演示

Java代码实现

import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
        int[] arr={6,3,2,9,8,1};
        System.out.println("排序前的数组为:");
        System.out.println(Arrays.toString(arr));
        //外层循环控制排序趟数
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = true;
            //内层循环控制每一趟排序多少次
            for (int j = 0; j arr[j+1]) {
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag = false;
                }
//                System.out.println(Arrays.toString(arr));
            }
            if (flag){
                break;
            }
//            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后的数组为:");
        System.out.println(Arrays.toString(arr));
    }
}

算法步骤分析

举例说明:要排序数组:int[] arr={6,3,8,2,9,1};   

第一趟排序:

    第一次排序:6和3比较,6大于3,交换位置: 3  6  8  2  9  1

    第二次排序:6和8比较,6小于8,不交换位置:3  6  8  2  9  1

    第三次排序:8和2比较,8大于2,交换位置:   3  6  2  8  9  1

    第四次排序:8和9比较,8小于9,不交换位置:3  6  2  8  9  1

    第五次排序:9和1比较:9大于1,交换位置:   3  6  2  8  1  9

    第一趟总共进行了5次比较, 排序结果:       3  6  2  8  1  9

第二趟排序:

    第一次排序:3和6比较,3小于6,不交换位置:3  6  2  8  1  9

    第二次排序:6和2比较,6大于2,交换位置:   3  2  6  8  1  9

    第三次排序:6和8比较,6大于8,不交换位置:3  2  6  8  1  9

    第四次排序:8和1比较,8大于1,交换位置:   3  2  6  1  8  9

    第二趟总共进行了4次比较, 排序结果:       3  2  6  1  8  9

第三趟排序:

    第一次排序:3和2比较,3大于2,交换位置:   2  3  6  1  8  9

    第二次排序:3和6比较,3小于6,不交换位置:2  3  6  1  8  9

    第三次排序:6和1比较,6大于1,交换位置:   2  3  1  6  8  9

    第二趟总共进行了3次比较, 排序结果:         2  3  1  6  8  9

第四趟排序:

    第一次排序:2和3比较,2小于3,不交换位置:2  3  1  6  8  9

    第二次排序:3和1比较,3大于1,交换位置:   2  1  3  6  8  9

    第二趟总共进行了2次比较, 排序结果:         2  1  3  6  8  9

第五趟排序:

    第一次排序:2和1比较,2大于1,交换位置:  1  2  3  6  8  9

    第二趟总共进行了1次比较, 排序结果:   1  2  3  6  8  9

最终结果:1  2  3  6  8  9

算法复杂性和稳定性

  1. 平均时间复杂度: O (n²)
  2. 最坏时间复杂度: O (n²)
  3. 最优时间复杂度: O(n)
  4. 空间复杂度:O(1)
  5. 稳定性:稳定

参考

维基百科: https://zh.wikipedia.org/wiki/冒泡排序

菜鸟教程: https://www.runoob.com/w3cnote/bubble-sort.html

博客园: https://www.cnblogs.com/shen-hua/p/5422676.html

除非注明,否则均为日常生活博客原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.mezgy.com/413.html

由日常生活

欣赏代码之美!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

有人回复时邮件通知我