排序算法 - 冒泡排序

冒泡排序算法应该可以说是很经典的一种对数据进行排序的的算法了，甚至在很多的介绍算法的数据中，它可能还是放在最前面开始讲解的。

冒泡排序算法到底是咋样的呢？冒泡这个说法又是怎么得来的呢？

首先先理解一下冒泡算法的实现原理。

冒泡算法的实现原理：是在一组散乱的数据中，按照升序或者降序的方式，不断的比较相邻的两个元素数据，如果第一个比第二个大（或者第一个比第二个小），就交换这两个数据元素的位置。

每一对相邻的数据元素都进行比较，交换位置，直到结尾的最后一对。这个过程就实现了将最大（最小）的元素放到最后的位置。

不断的重复上面的步骤，最后就能将数据中的最大（最小）的元素放到最后。这个过程就像是水里的泡泡产生的过程，最底下的最小，在上升过程中逐渐变大，直到最后冒出水面的泡泡是最大的。也许这就是冒泡算法的名字由来吧！

冒泡算法的实现过程可以用下面的动图演示一下：

上图中的演示就是按照将数据按照从小到大的顺序进行排列，最终要实现最后的那个位置的元素需要时最大的目的。这个过程就像冒泡一样。

冒泡排序算法什么时候能最快完成排序和最慢排成排序？（我这里以升序为例说明）

最快的时候应该是在所需要排序的数据正好正序的时候了，这个时候不需要进行任何数据的交换。

最慢的时候应该是在数据正好是反序的时候，这个时候每一对相邻的数据都需要进行一次交换排序，也是费时间最长的。

用C语言实现的简单冒泡算法如下：(升序为例)

void maopao_sort(int *arr,int len)
{
    int i,j,temp;
    for(i=0;i<len-1;i++)
    {
        for(j=0;j<len-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

从程序中可以看的出来，假如共有 n 个数据进行排序，冒泡排序算法最终要实现的排序次数为 n-1次。

那如果在排序中，经过几次排序就已经完成了数据的排序，那之后的几次都不需要检查数据了，那岂不是有好几次是在“空跑”？这样浪费了一些时间，这种情况最好能做点优化。

优化后的代码如下：

void maopao_sort(int *arr,int len)
{
    int needSortFlag = 0;
    int i,j,temp;
    for(i=0;i<len-1;i++)
    {
        for(j=0;j<len-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                needSortFlag = 1;
            }
        }
        if(!needSortFlag) break;
    }
}