手机版
你好,游客 登录 注册
背景:
阅读新闻

Java八大排序算法之冒泡排序

[日期:2019-08-04] 来源:Linux社区  作者:十八岁 [字体: ]

一、动图演示

二、思路分析

1.  相邻两个数两两相比,n[i]跟n[j+1]比,如果n[i]>n[j+1],则将连个数进行交换,

2.  j++, 重复以上步骤,第一趟结束后,最大数就会被确定在最后一位,这就是冒泡排序又称大(小)数沉底,

3.  i++,重复以上步骤,直到i=n-1结束,排序完成。

三、负杂度分析

1.  不管原始数组是否有序,时间复杂度都是O(n2),

因为没一个数都要与其他数比较一次,(n-1)2次,分解:n2+2n-1,  去掉低次幂和常数,剩下n2,所以最后的时间复杂度是n2

2.  空间复杂度是O(1),因为只定义了一个辅助变量,与n的大小无关,所以空间复杂度为O(1)

四、 选择排序和冒泡排序的比较

1. 时间负责度都是O(n2)

2. 空间复杂度都是O(1)

3. 选择排序是从第一位开始确定最大或最小的数,保证前面的数都是有序的,且都比后面的数小或大,

  冒泡排序是从最后一位开始确定最大或最小的数,保证后面的数都是有序的且都大于或小于前面的数。

五、Java 代码如下

import java.util.Arrays;
public class 冒泡 {
    public static void main(String[] args) {
        int[] n = new int[]{1,6,3,8,33,27,66,9,7,88};
        int temp;
        for (int i = 0; i < n.length-1; i++) {
            for (int j = 0; j <n.length-1; j++) {
                if(n[j]>n[j+1]){
                    temp = n[j];
                    n[j] = n[j+1];
                    n[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(n));
    }
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-08/159807.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款