目录

一、排序过程

二、代码

三、性能及稳定性分析

1.空间复杂度

2.时间复杂度

3.稳定性

一、排序过程

从后往前(从前往后)两两比较相邻元素的值，如果前面元素大于后面元素，则交换他们的位置(升序)。

如果结果需要降序则当前面元素小于后面元素时对他们进行交换。

直到序列比较完，这叫做第一趟排序。结果是确定了最小的元素的位置(第一个位置)，下一趟排序的时候已经确定位置的元素就不需要进行比较。整个过程就如同气泡一样慢慢往上漂浮。

二、代码

package sort;

public class BubboSort {
    public static void main(String[] args) {
        int[] arr = {3, 6, 4, 1, 9, 6, 5, 8, 7, 2};
        System.out.print("排序前为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        bubbosort(arr);
        System.out.print("排序后为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

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

第一趟排序过程：

结果：

三、性能及稳定性分析

1.空间复杂度

因为排序的整个过程中，仅在当前的数组中操作，没有使用另一个空数组，仅使用了常熟个辅助单元，因此时间复杂度为O(1)。

2.时间复杂度

• 最好情况：当初始序列有序时，只需要进行一趟比较，所以时间复杂度为O(n)。
• 最坏情况：当初始序列和结果序列成逆序时，需要进行n-1趟排序，第i趟排序需要进行n-i次关键字的比较。时间复杂度为O()

所以冒泡排序的平均时间复杂度为O()。 

3.稳定性

由上上图对冒泡排序第一趟的分析，黑色的6开始在前面红色的6在后面，而排完序后黑色的6仍然在红色6的前面，因此冒泡排序是一个稳定的排序。