BubbleSort（冒泡排序）

顾名思义，冒泡排序法就是让数组元素像水中的气泡一样逐渐上浮，进而达到排序的目的。下面算法便是利用冒泡法将数列排列为升序的例子：

    flag=1       //存放顺序相反的相邻元素
    while flag
        flag=0
        for j 从N-1到 1
        if A[j]<A[j-1]
            A[j] 与 A[j-1] 交换
            flag=1

讲解：
与之前的插入法排序一样，冒泡排序法的各个计算步骤中，数组也分为“已排序部分“和“未排序部分”。

冒泡排序法：
重复执行下述处理，知道数组中不包含顺序相反的相邻元素

从数组末尾开始依次比较相邻的两个元素，如果大小关系相反，则交换两个元素的位置。
下面以数组A={5,3,2,4,1}为例，对其进行冒泡排序，具体排序过程如下：

排序.jpg

数组从开头逐一完成排序。步骤一到步骤四的处理结束后，数据中最小的元素将移动到数组开头的A[0]位置。同理，步骤五到步骤七结束后，第二小元素移动到A[1]，然后步骤八到步骤九确定A[2]，步骤十确定A[3]，依次往下，逐一确定已排序部分末尾要追加的元素。
程序每完成一次外层循环，已排序部分就增加一个元素。这样外层循环最多执行N次，同事内层循环执行次数会逐渐减少。所以又可得冒泡排序算法：

    flag=1
    i=0;    //未排序部分的起始下标
    while flag
        flag=0
        for j 从N-1到 i+1
            if A[j]<A[j-1]
                A[j] 与 A[j-1] 交换
                flag=1
        i++

总结：
冒泡排序法仅对数组中相邻元素进行比较和交换，因此键相同的元素不会改变顺序。所以其属于一种稳定排序的算法。但，一旦将比较运算A[j]<A[j-1]改为A[j]<=A[j-1]，算法就会失去其稳定性。