动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

Java排序算法之冒泡排序

05-12 10:57 396浏览
举报 T字号
  • 大字
  • 中字
  • 小字

冒泡排序(Bubble Sort)是一种较为简单的排序算法。它重复访问要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换的数据,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,像水中的气泡从水底浮到水面,,就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

1.算法描述

冒泡排序算法的算法过程如下:

(1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

(2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

(3) 针对所有的元素重复以上的步骤,除了最后一个。

(4)持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。

2.代码实现

package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * Created by zhoujunfu on 2018/8/2.
 */
public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        //外层:需要length-1次循环比较
        for (int i = 0; i < length - 1; i++) {
            //内层:每次循环需要两两比较的次数,每次比较后,都会将当前最大的数放到最后位置,所以每次比较次数递减一次
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    //交换数组array的j和j+1位置的数据
                    swap(array, j, j+1);
                }
            }
        }
    }

    /**
     * 交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

3.算法效率

冒泡排序是稳定的排序算法,最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²)。最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n)。平均来讲, 时间复杂度为O(n²),由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(n2) O(n) O(n2) O(1)

4.交换数字的三种方法

我们从冒泡排序的代码中看到了交换两个数字的方法 swap(int[] array, int i, int j),这里使用了临时变量,而交换数字主要有三种方法,临时变量法、算术法、位运算法、面试中经常会问到,这里简单说一下,代码如下:

package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/9/10.
 */
public class SwapDemo {

    public static void main(String[] args) {
        // 临时变量法
        int[] array = new int[]{10, 20};
        System.out.println(Arrays.toString(array));
        swapByTemp(array, 0, 1);
        System.out.println(Arrays.toString(array));
        
        // 算术法
        array = new int[]{10, 20};
        swapByArithmetic(array, 0, 1);
        System.out.println(Arrays.toString(array));
        
        // 位运算法
        array = new int[]{10, 20};
        swapByBitOperation(array, 0, 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 通过临时变量交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swapByTemp(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 通过算术法交换数组array的i和j位置的数据(有可能溢出)
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void  swapByArithmetic(int[] array, int i, int j) {
        array[i] = array[i] + array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }


    /**
     * 通过位运算法交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void  swapByBitOperation(int[] array, int i, int j) {
        array[i] = array[i]^array[j];
        array[j] = array[i]^array[j]; //array[i]^array[j]^array[j]=array[i]
        array[i] = array[i]^array[j]; //array[i]^array[j]^array[i]=array[j]
    }
}

冒泡排序算是Java众多排序算法中比较简单的了,所以,作为我们学习排序算法的着手点。动力节点在线的视频课程中对各种排序算法都有很详细的讲解,想学习的小伙伴千万不要错过哦。

0人推荐
共同学习,写下你的评论
0条评论
代码小兵498
程序员代码小兵498

153篇文章贡献528999字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消