冒泡排序优化算法c++

冒泡排序是一种简单但效率较低的排序算法，其基本思想是通过相邻元素的比较和交换来将较大的元素逐渐“浮”到数组的末尾。冒泡排序的时间复杂度为O(n^2)。

在冒泡排序的基础上，可以进行一些优化来提高算法的效率。以下是两种常见的冒泡排序优化算法：

1. 设置标志位：在每一轮的比较中，如果没有发生元素交换，则说明数组已经有序，可以提前结束排序。

   void bubbleSort(int arr[], int n) {
       bool flag = true; // 标志位
       for (int i = 0; i < n - 1 && flag; ++i) {
           flag = false;
           for (int j = 0; j < n - i - 1; ++j) {
               if (arr[j] > arr[j + 1]) {
                   swap(arr[j], arr[j + 1]);
                   flag = true;
               }
           }
       }
   }

2. 记录最后一次交换位置：在每一轮的比较中，记录最后一次发生元素交换的位置，下一轮比较只需要进行到该位置即可。

   void bubbleSort(int arr[], int n) {
       int lastSwapIndex = n - 1; // 最后一次交换位置
       int k;
       while (lastSwapIndex > 0) {
           k = lastSwapIndex;
           lastSwapIndex = 0;
           for (int j = 0; j < k; ++j) {
               if (arr[j] > arr[j + 1]) {
                   swap(arr[j], arr[j + 1]);
                   lastSwapIndex = j;
               }
           }
       }
   }