Java 数组的冒泡排序

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

package com.cyj.demo;

/**
 * 
 * Function：
 * Author：@author chenyongjia
 * Date：2019-11-04 23:15
 * 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;
    }
}

说明

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

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