冒泡排序时间复杂度最坏情况_冒泡排序时间复杂度怎么计算

冒泡排序是一种基础且经典的排序方法，它运用“冒泡策略”的原理，逐步将最大的元素移至序列的最右端。得名于其排序过程，犹如碳酸饮料中气泡的升浮，愈大的元素愈能"浮"至数列的顶端。这一过程正如升序或降序排列所需，每次只交换相邻的元素。如果左边的元素大于右边的元素，它们便会进行位置互换。

1. 遍历序列，比较相邻的两个元素。若首位的元素大于第二位的元素，则进行位置的互换。
2. 重复此步骤于每一对相邻的元素，从序列的起始对到末尾的结束对。这样操作后，最大的数将会移动至序列的最后。
3. 针对除最后一个以外的所有元素重复上述步骤。
4. 继续重复上述步骤，每次针对越来越少的元素进行操作，直至没有哪一对数字需要再进行比较。

时间复杂度

在文件的初始状态为正序的情况下，一次扫描便能完成排序，这时所需的关键字比较次数和记录移动次数达到最小值。冒泡排序的最佳时间复杂度为O(n)。

相反，若初始文件为反序状态，则需进行n-1轮排序。每轮中需进行n-i次关键字比较（1≤i≤n-1），且每次比较后都需要移动记录三次来交换位置。比较和移动次数达到最大值。

综上，冒泡排序的平均时间复杂度为O(n^2)。

算法稳定性

模板定义如下（适用于整数或浮点数）:

template<typename T>
void bubble_sort(T arr[], int len) {
    int i, j;
    T temp;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }