【C语言】十大排序之冒泡排序（三种优化）

目录

冒泡排序概念

基础代码演示

第一种优化方式，加入flag判断最大数有多少已经排好

第二种优化方式，双向冒泡

第三种优化方式，设立flag加双向冒泡

冒泡排序概念

(Bubble Sort)是一种简单排序，在最坏情况下时间复杂度为O(n^{2}）。原理为依次判断两个相邻的数，如果错误就将他们换位，并依次走访数列，直到每一个数都在正确的位置上。

动图演示：（图片来自网络，侵删）

基础代码演示

void bubble(int num[], int size)
{
    int i, j, temp;
    for(i = 0; i < size - 1; i++)
    {
        for(j = 0; j < size - 1 - i; j++)
        {
            if(num[j] > num[j+1])//满足条件就交换位置
            {
                temp = num[j];
                num [j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
}

在这里我们可以加入flag判断是否完成 ，如果已经完全排好序，就不用进行之后的步骤了：

void bubble(int num[], int size)
{
    int i, j, temp, flag;

    for(i = 0; i < size - 1; i++)
    {
        flag = 0;
        for(j = 0; j < size - 1 - i; j++)
        {
            if(num[j] > num[j+1])
            {
                temp = num[j];
                num [j] = num[j+1];
                num[j+1] = temp;
                flag = 1;
            }
        }
        if(!flag)如果flag没有变化，则说明这一次没有进行排序，即所有数已经排好，执行退出
        {
            break;
        }
    }
}

第一种优化方式，加入flag判断最大数有多少已经排好

前面加入flag的思想，是如果在过程中就排好所有的序就退出，但是在实际中，这种情况其实出现的很少，那么我们是否可以改变一下，记录每次已经排好的数的下标，下一次排序就只需要排序到记录的下标即可？

实现代码：

void bubble(int num[], int size)
{
    int i, j, k, temp, flag;
    flag = size - 1;

    while(flag > 0)
    {
        k = flag;//初始化为size-1，以后每一次取出flag
        flag = 0;//每一次flag重置为0

        for(i = 0; i < k; i++)
        {
            if(num[i] > num[i+1])
            {
                temp = num[i];
                num[i] = num[i+1];
                num[i+1] = temp;
                flag = i;//i最终的值为最后被排序的下标
            }
        }
    }
}

第二种优化方式，双向冒泡

第二种优化方式为同时进行上浮和下沉，思想和普通的冒泡没有本质区别。

实现代码：

void bubble(int num[], int size)
{
    int i, j, k, temp, flag;

    for(i = 0; i < size / 2; i++)//因为双向同时进行，所以只需要size/2次大循环
    {
        flag = 0;
        for(j = 0; j < size - i - 1; j++)//从前往后排
        {
            if(num[j] > num[j+1])
            {
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
                flag = 1;
            }
        }
        for(k = size - 1 - i; k > 0; k--)//从后往前排
        {
            if(num[k] < num[k-1])
            {
                temp = num[k];
                num[k] = num[k-1];
                num[k-1] = temp;
                flag = 1;
            }
        }

        if(!flag)
        {
            break;
        }
    }
}

第三种优化方式，设立flag加双向冒泡

通过思考前面的两种优化，我们是否可以将记录下标和双向冒泡结合？

如果从前往后排列到某一个数就没有再发生变化，那么该下标之后的数都已经排好序，那么从后往前就只用从改下标往前排序即可。同理，从后往前排列到某一个数就没有再发生变化，那么该下标之前的数都已经排好序，那么只需从该下标往后排序。

实现代码：

void bubble(int num[], int size)
{
    int i, j, k, up, down, temp, flag;
    up = size - 1;
    down = 0;
    for(i = size - 1; i > 0; i--)//从前往后排
    {
        for(j = down; j < up; j++)
        {
            if(num[j] > num[j+1])
            {
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
                flag = j;//取出从前往后的下标，在下标之后的数都已经排好序
            }
        }

            if(flag == -1)
            {
                break;
            }
            up = flag;//取出flag的值
            flag = -1;//重置flag

            for(k = up; k > down; k--)
            {
                if(num[k] < num[k-1])
                {
                    temp = num[k];
                    num[k] = num[k-1];
                    num[k-1] = temp;
                    flag = k;//取出从后往前的下标，在下标之前的数都已经排好序
                }
            }

            if(flag == -1)
            {
                break;
            }
            down = flag;//取出flag的值
            flag = -1;//重置flag
    }
}

总结

冒泡排序可以通过加flag取下标来减少判断的次数，以及双向排序减少大循环的次数，这两种优化可以结合起来。

纯手打，水平有限，如有疏漏，欢迎指教讨论。