冒泡排序复杂度分析及优化 - 时间复杂度降至O(n)

冒泡排序是一种简单直观的排序算法，其时间复杂度为O(n^2)，其中n是数组的长度。这是因为它使用了两层嵌套循环，每次比较相邻的两个元素并进行交换，共需要进行n-1轮比较和交换，每轮比较和交换的次数也逐渐减少。

然而，冒泡排序的性能可以进行优化。可以使用一个标志位来记录每一轮是否发生了交换，如果没有发生交换，说明数组已经有序，可以提前结束排序。这样可以减少不必要的比较和交换操作，提高排序的效率。

以下是优化后的冒泡排序代码：

public class InventorySort {

    public static void main(String[] args) {
        int[] inventory = {5, 8, 2, 10, 3};
        inventorySort(inventory);
        for (int i = 0; i < inventory.length; i++) {
            System.out.print(inventory[i] + " ");
        }
    }

    // 库存排序方法
    public static void inventorySort(int[] inventory) {
        for (int i = 1; i < inventory.length; i++) {
            boolean isSorted = true;
            for (int j = 0; j < inventory.length - i; j++) {
                if (inventory[j] < inventory[j + 1]) {
                    int temp = inventory[j];
                    inventory[j] = inventory[j + 1];
                    inventory[j + 1] = temp;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }
}

优化后的冒泡排序在最好的情况下（数组已经有序）的时间复杂度为O(n)，在最坏的情况下（数组逆序）的时间复杂度仍然是O(n^2)，但是平均情况下的时间复杂度会有所降低。