利用逆序数计算冒泡排序的复杂度

### 使用逆序数分析冒泡排序的时间复杂度

对于给定的一个数组，其内部存在的逆序对数量直接影响到冒泡排序所需执行的操作次数。具体来说，在每一趟遍历过程中，冒泡排序会逐步减少这些逆序对的数量直到全部消除为止。

在一个长度为 \(n\) 的数组里，如果有大量的逆序对存在，则意味着更多的元素需要被交换位置才能达到最终的有序状态。当数组处于完全逆序的情况下，即每一个可能的位置组合都构成了一组新的逆序对时，此时该数组拥有最大量的逆序对数目\[ \frac{n(n-1)}{2} \][^3]。这种情况下，为了使整个序列变得有序，冒泡排序不得不做尽可能多的工作——每一次迭代都要处理几乎所有的剩余逆序对，从而导致性能下降至最差情形下的时间复杂度\(O(n^{2})\)[^4]。

另一方面，考虑最佳情况，也就是原始数据已经部分甚至全部有序的情形下，由于初始状态下就几乎没有或者完全没有逆序对的存在，那么即使采用未经任何优化的传统版冒泡排序方法也能够迅速完成任务，仅需线性时间内即可结束运算过程[^5]。

综上所述，利用逆序数可以很好地解释为什么不同输入条件下冒泡排序表现出不同的效率特征：随着待排序列中逆序对数量增加，算法所消耗的时间也会相应增长；反之亦然。

def count_inversions(arr):
    inv_count = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] > arr[j]:
                inv_count += 1
    return inv_count


# 测试函数
test_array = [64, 34, 25, 12, 22, 11, 90]
print(f"The number of inversion pairs is {count_inversions(test_array)}.")