深入理解冒泡排序

冒泡排序

冒泡排序核心思想重复比较相邻元素，将大的往后交换；空间复杂度O(1)；时间复杂度平均O(n²)，最好O(n)；相对稳定，简单效率低适合小规模数据。

//冒泡排序基本版本实现
bubbleSort(std::vector<int> arr)
{
    int n = arr.size();
    if(n<=1)
    {
        return;
    }
    for(int i=0; i<n-1; i++)
    {
        //每次循环将最大的元素“冒泡”到最后
        for(int j=0; j<n-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

/*优化版本冒泡排序
 *优化点1：减少内循环范围（已经排序部分不再比较）
*/
bubbleSort(std::vector<int> arr)
{
    int n = arr.size();
    if(n<=1)
    {
        return;
    }
    for(int i=0; i<n-1; i++)
    {
        // 每轮排序后，最大的元素会沉到底部
    	// 所以内循环范围可以逐渐减小
        for(int j=0; j<n-1-i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

/*优化版本冒泡排序
 *优化点2：添加交换标志（如果一轮没有交换，说明排序已经完成）
*/
bubbleSort(std::vector<int> arr)
{
    int n = arr.size();
    bool swapped;
  
    if(n<=1)
    {
        return;
    }
    for(int i=0; i<n-1; i++)
    {
        swapped = false;
        //每次循环将最大的元素“冒泡”到最后
        for(int j=0; j<n-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                std::swap(arr[j], arr[j+1]);
                swapped = true;// 标记发生了交换
            }
        }
        if(!swapped)
        {
            break;
        }
    }
}

/*优化版本冒泡排序
 *优化点3：记录最后一次交换位置（缩小下次循环范围）
*/
bubbleSort(std::vector<int> arr)
{
    int n = arr.size();
    int lastSwapIndex = n - 1;  // 初始边界
    if(n<=1)
    {
        return;
    }
    while(lastSwapIndex>0)
    {
        int k = 0;  // 记录本轮最后交换位置
  
        //每次循环将最大的元素“冒泡”到最后
        for(int j=0; j<n-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                std::swap(arr[j], arr[j+1]);
                k=j;
            }
        }
        lastSwapIndex = k;
    }
}

/*优化版本冒泡排序
 *优化点4：双向冒泡排序（鸡尾酒排序）
*/
bubbleSort(std::vector<int> arr)
{
    int n = arr.size();
    int left = 0, right = n - 1; 
    if(n<=1)
    {
        return;
    }
    while(left < right)
    {   
        // 从左向右冒泡（大元素向右移动）
        for(int j=left; j<right; j++)
        {
            if(arr[j] > arr[j+1])
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
        right--;  // 右边界缩小
  
         // 从左向右冒泡（大元素向右移动）
        for(int j=right; j>left; j--)
        {
            if(arr[j] <  arr[j-1])
            {
                std::swap(arr[j], arr[j+1]);
            }
        }
        left++;  // 左边界增大
  
        // 每轮完成后，左右边界各缩小一个位置
    }
}

/*综合优化版本冒泡排序
 *优化点1：减少内循环范围（已经排序部分不再比较）
 *优化点2：添加交换标志（如果一轮没有交换，说明排序已经完成）
 *优化点3：记录最后一次交换位置（缩小下次循环范围）
 *优化点4：双向冒泡排序（鸡尾酒排序）
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * 综合优化的冒泡排序
 * 结合了标志位、记录最后交换位置、双向冒泡等优化
 */
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;
  
    int left = 0;                 // 左边界
    int right = n - 1;            // 右边界
    int lastSwapIndex = 0;        // 记录最后交换位置
    bool swapped = true;          // 交换标志
    bool forward = true;          // 方向标志（双向冒泡）
  
    while (swapped) {
        swapped = false;
  
        if (forward) {
            // 正向冒泡：从左到右
            for (int i = left; i < right; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr[i], arr[i + 1]);
                    swapped = true;
                    lastSwapIndex = i;  // 记录最后交换位置
                }
            }
            right = lastSwapIndex;  // 更新右边界
        } else {
            // 反向冒泡：从右到左
            for (int i = right; i > left; i--) {
                if (arr[i] < arr[i - 1]) {
                    swap(arr[i], arr[i - 1]);
                    swapped = true;
                    lastSwapIndex = i;  // 记录最后交换位置
                }
            }
            left = lastSwapIndex;  // 更新左边界
        }
  
        // 切换方向
        forward = !forward;
    }
}