冒泡排序及其简单优化

冒泡排序是最基础的排序算法，每一轮的冒泡都是把最小的或者最大的冒到一端，是一种稳定的排序算法，时间复杂度为O(n^2)

原始的冒泡排序

    //冒泡排序
    void BubbleSort1(int* arr, int size)
    {
        int i = 0, j = 0;
    
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            for (j = 0; j < size - 1 - i; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    
    }

优化一：优化外层循环

在某一次外层循环发现没有发生交换时说明冒泡已经结束，因为接下来的循环区间都比这一次的要小，所以接下来的冒泡就无意义，则提前退出循环。优化后的冒泡排序最好时间复杂度是O(n),最坏时间复杂度是O(n^{2)，平均时间复杂度是O(n}2)

    //冒泡排序优化1
    void BubbleSort2(int* arr, int size)
    {
        int i = 0, j = 0;
    
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            //每次遍历标志位都要先置为0，才能判断后面的元素是否发生了交换
            int flag = 0;
    
            for (j = 0; j < size - 1 - i; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = 1;//只要有发生了交换，flag就置为1
                }
            }
    
            //判断标志位是否为0，如果为0，说明后面的元素已经有序，就直接return
            if (flag == 0)
            {
                return;
            }
        }
    }
    

优化2：优化内层循环

在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之后的相邻记录均已有序，因为正在冒的数是当前最小的，如果该数停止往上冒了，且后面没有冒泡的操作了，说明后面的数比这个数都小，且已经排好序）。下一趟排序开始时，R[1..lastExchange-1]是无序区，R[lastExchange..n]是有序区。这样，一趟排序可能使当前无序区扩充多个记录，因此记住最后一次交换发生的位置lastExchange，从而减少排序的趟数。

    void BubbleSort3(int* arr, int size)
    {
        int i = 0, j = 0;
        int k = size - 1,pos = 0;//pos变量用来标记循环里最后一次交换的位置  
        
        for (i = 0; i < size - 1; i++)//一共要排序size-1次
        {
            //每次遍历标志位都要先置为0，才能判断后面的元素是否发生了交换
            int flag = 0;
    
            for (j = 0; j <k; j++)//选出该趟排序的最大值往后移动
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = 1;//只要有发生了交换，flag就置为1
                    pos = j;//循环里最后一次交换的位置 j赋给pos
                }
            }
    
            k = pos;
            //判断标志位是否为0，如果为0，说明后面的元素已经有序，就直接return
            if (flag == 0)
            {
                return;
            }
        }
    }