欢迎光临
我们一起进阶

Java 数组(三):冒泡排序

扫码或搜索:沉默王二
发送 290992
即可立即永久解锁本站全部文章

Java 数组的冒泡排序

冒泡排序的基本思想是通过比较相邻数据的大小,来判断是否交互位置,通过第一轮遍历比较,找到最大的,或者最小的值,并且交换到列表的尾部。循环多次将无无序列表进行排序。

如下:

代码实现

package com.silence.arts.xiaobai;

/**
 * 
 * Function:
 * Author:@author ziyou
 * Date:2019-07-29 22:29
 * Desc:无
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        int[] ints = bubbleSort(array);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public static int[] bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }
}

说明

冒泡排序的形式有很多种,上面只是提供的一种思路,还有其他方式,小伙伴可以自行去尝试。

  1. 时间复杂度
    在设置标志变量之后:
    当原始序列“正序”排列时,冒泡排序总的比较次数为n-1,移动次数为0,也就是说冒泡排序在最好情况下的时间复杂度为O(n);
    当原始序列“逆序”排序时,冒泡排序总的比较次数为n(n-1)/2,移动次数为3n(n-1)/2次,所以冒泡排序在最坏情况下的时间复杂度为O(n^2);
    当原始序列杂乱无序时,冒泡排序的平均时间复杂度为O(n^2)。
  2. 空间复杂度
    冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。
  3. 稳定性
    冒泡排序在排序过程中,元素两两交换时,相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

赞(0) 打赏
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

小白学堂,学的不止是技术,更是前程

关于我们免责声明

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏