广告
返回顶部
首页 > 资讯 > 后端开发 > Python >JAVA十大排序算法之冒泡排序详解
  • 902
分享到

JAVA十大排序算法之冒泡排序详解

JAVAJAVA冒泡排序 2022-11-12 10:11:03 902人浏览 泡泡鱼

Python 官方文档:入门教程 => 点击学习

摘要

目录冒泡排序代码实现代码实现时间复杂度算法稳定性总结冒泡排序 1.从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个 2.对每一对相邻元素作同样的工作,从开始第

冒泡排序

1.从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个

2.对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数

3.重复步骤1~2,重复次数等于数组的长度,直到排序完成

image-20210728113340011

代码实现

对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

代码实现


public class BubbleSort {
    public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //array.length - 1 -i 已经冒泡到合适位置无需在进行排序,减少比较次数
            for (int j = 0; j < array.length - 1 -i; j++) {
                //前面的数大于后面的数交换
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
}

时间复杂度

对于上面12个数据项,从第一个元素开始,第一趟比较了11次,第二趟比较了10次,依次类推,一直到最后一趟,就是:

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66次

若有n个元素,则第一趟比较为(n-1)次,第二趟比较为(n-2)次,依次类推:

(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2

在大O表示法中,去掉常数系数和低阶项,该排序方式的时间复杂度为:O(n2)

算法稳定性

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。——百度百科

在代码中可以看到,array[j + 1] = array[j]的时候,我们可以不移动array[i]和array[j],所以冒泡排序是稳定的。

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注编程网的更多内容!

--结束END--

本文标题: JAVA十大排序算法之冒泡排序详解

本文链接: https://www.lsjlt.com/news/133272.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作