89、排序算法中的冒泡排序，怎么优化冒泡排序？时间复杂度？

冒泡排序是一种简单的排序算法，它的基本思想是重复地遍历要排序的数列，比较每对相邻元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

优化冒泡排序的方法主要有以下几种：

1. **引入标志位**：在遍历过程中，如果没有发生过交换，说明序列已经是有序的，可以直接结束排序，无需继续检查剩余元素。这可以减少不必要的比较次数。

bool swapped;
do {
    swapped = false;
    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            std::swap(arr[i], arr[i + 1]);
            swapped = true;
        }
    }
} while (swapped);

2. **优化内层循环**：当数组已经是升序时，可以在检测到最后一个元素正确的位置后提前终止内层循环。同样，在降序排列的情况下，如果当前元素小于或等于下一个元素，则不需要交换，直接跳过。

3. **混合式冒泡排序**：结合插入排序，对于小规模数据或部分有序的数据，当数组长度较小或者经过一定轮次后未发生交换，可以切换为插入排序，提高效率。

冒泡排序的时间复杂度是O(n^2)，其中n是要排序的元素个数。这是因为在最坏情况下（数组完全逆序），需要进行n-1轮比较，每轮都需要比较n-i次，所以总共是(n-1) * (n-1) = n^2 - 2n + 1。平均情况下的时间复杂度也是O(n^2)。由于其效率较低，不适合处理大规模数据。