冒泡排序

冒泡排序是最基本的排序方式，是在每次遍历时，通过交换相邻元素将未排序元素中最大元素（最小元素）沉下去（浮上来）的过程。

一、经典的冒泡排序：

void bubble(vector<int>& nums)
{
    int size = nums.size();
    //外层循环：每次循环排序好一个元素
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 1; j < size - i; j++)
        {
            if (nums[j] < nums[j - 1])
            {
                swap(nums, j, j - 1);
            }
        }
    }
}

二、优化

1. 阻止数组排好序之后无意义的循环

上面经典冒泡排序法在数组的数据已经排好的情况下，仍会继续进行下一轮循环遍历，进行无意义的循环，通过增加标记位来处理这种情况

void bubble(vector<int>& nums)
{
    int size = nums.size();
    bool has_sorted = false;    //记录nums是否已经是排序数组的标记
    for (int i = 0; i < size - 1 && !has_sorted; i++)
    {
        has_sorted = true;
        for (int j = 1; j < size - i; j++)
        {
            if (nums[j] < nums[j - 1])
            {
                has_sorted = false;
                swap(nums, j, j - 1);
            }
        }
    }
}

2. 优化内层循环

每次记住每趟第一次交换的位置和最后一次交换的位置，第一次交换位置之前的元素都已经排好序了，同理，最后一次交换的位置之后的元素都已经排好序了

void bubble_sort( vector<int>& nums )
{
    int size = nums.size();
    int last_swap_end = size - 1, last_swap_start = 0;
    int q = size -1;
    int p = last_swap_start;
    int first_flag = 1;     //记录是否为第一次交换
    for ( int i = 0; i < size-1; i++ )
    {
        for ( int j = p; j < q; j++ )
        {
            if ( nums[j] > nums[j+1] )
            {
                swap(nums[j], nums[j+1]);
                last_swap_end = j;
                if ( first_flag )
                {
                    last_swap_start = j == 0 ? 0 : j -1;
                    first_flag = 0;
                }
            }
        }
        q = last_swap_end;
        first_flag = 1;
        p = last_swap_start;
    }
}

3. 双向冒泡排序法（鸡尾酒排序法）

鸡尾酒排序是冒泡排序的一种改进和变型 ，又称“双向冒泡排序”，鸡尾酒排序是从低到高然后从高到低来回排序（选出最大和最小项），比冒泡排序的效率稍微好一点，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目

// 鸡尾酒排序(C++)
void CockTailSort(vector<int> &vi)
{
    int isSorted=false;
    //双向同时进行
    for(int i = 0; i < vi.size()/2 && !isSorted; i++)
    {
        isSorted = true;
        //升序排列
        for(int j = i;j < vi.size()-i-1; j++)
        {
            if(vi[j] > vi[j+1])
            {
                swap(vi[j], vi[j + 1]);
                isSorted = false;
            }
        }

        //降序排列
        for(int j = vi.size()-i-1; j>i; j--)
        {
            if(vi[j] < vi[j-1])
            {
                swap(vi[j], vi[j - 1]);
                isSorted = false;
            }
        }
    }
}

三、性能分析

• 平均时间复杂度：O(N²)
• 最坏时间复杂度：O(N²)，出现在当前数组被逆序排序
• 最好时间复杂度：O(N)，出现在优化1的版本中，输入的数组已经被排好序时
• 稳定性：稳定，相等元素在排序前后保持相对位置不变