冒泡排序算法图文详解

冒泡排序又称起泡排序，是最容易实现的一种排序算法，时间复杂度为O(n2)。

冒泡排序算法的工作原理是：反复遍历待排序的目标序列，过程中不断比较相邻元素的值，对于违背升序或降序规则的相邻元素，互换它们的位置。直至各相邻元素不再需要互换位置，则排序结束。

此排序算法每次遍历待排序序列，都会从序列中筛选出一个最大值或者最小值，这也是将该排序算法称为“冒泡”或者“起泡”的原因。

举个例子，假设有一个待排序序列 {14,33,27,35,10}，使用冒泡排序算法对其进行升序（由小到大）排序的过程如下：

1、第一次遍历整个序列：
1) 比较相邻元素 14 和 33 的值，显然 14 < 33，符合升序的要求，无需交换它们的位置，序列保持原样。

2) 继续比较相邻元素 33 和 27 的值，33 > 27，不符合升序的要求，交换它们的位置，新序列如下所示：

3) 继续比较相邻元素 33 和 35 的值，33 < 35，符合升序的要求，序列保持原样。

4) 继续比较相邻元素 35 和 10 的值，35 < 10，不符合升序的要求，交换它们的位置，新序列如下所示：

由此，从待排序序列中筛选出了最大值 35，并将其置于待排序序列的末尾。

2、第二次遍历：
待排序序列变为 {14 , 27 , 33 , 10}，继续采用相同的办法遍历该序列，最终得到的新序列为：

3、第三次遍历：
待排序序列变成 {14 , 27 , 10}，继续采用相同的方法遍历该序列，最终得到的新序列为：

4、第四次遍历：
待排序序列变为 {14,10}，继续采用相同的方法遍历该序列，最终得到的新序列为：

至此，整个序列变为升序序列。

冒泡排序算法的具体实现

如下为冒泡排序算法实现升序排序的伪代码：

Bubble_sort(list):                           // list 表示待排序序列
    for i <- 1 to length(list):            // list 序列中有多少个元素，就遍历多少遍（最后一遍不做任何操作）
        for j <- 1 to length(list) - i:    // 从第 1 个元素开始遍历，遍历至第 length(list) -i 个元素
            if list[j] > list[j+1]:              // 若进行降序排序，则改成 < 小于号
                 swap(list[j] , list[j+1])    // 交换 2 个相邻元素的位置
    return list                                   // 返回排好序的序列

如下为用冒泡排序算法对 {14,33,27,35,10} 进行升序排序的 C 语言程序：

#include<stdio.h>
#define N 5    //设定待排序序列中的元素个数
//实现冒泡升序排序算法的函数，list[N] 为待排序数组
void Bubble_sort(int list[N]) {
    int i, j;
    int temp = 0;
    // N 个元素，遍历 N 次
    for (i = 0; i < N; i++) {
        // 从第 1 个元素开始遍历，遍历至 N-1-i
        for (j = 0; j < N - 1 - i; j++) {
            //比较 list[j] 和 list[j++] 的大小
            if (list[j] > list[j + 1]) {
                //交换 2 个元素的位置
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}
int main() {
    int i = 0;
    int list[N] = { 14,33,27,35,10 };
    Bubble_sort(list);
    //输出已排好序的序列
    for (i = 0; i < N; i++) {
        printf("%d ", list[i]);
    }
    return 0;
}

如下为用冒泡排序算法对 {14,33,27,35,10} 进行升序排序的 Java 程序：

public class Demo {
    public static void Bubble_sort(int[] list) {
        int length = list.length;
        // length 个元素，遍历 length 次
        for (int i = 0; i < length; i++) {
            // 从第 1 个元素开始遍历，遍历至 length-1-i
            for (int j = 0; j < length - 1 - i; j++) {
                // 比较 list[j] 和 list[j++] 的大小
                if (list[j] > list[j + 1]) {
                    // 交换 2 个元素的位置
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] list = { 14, 33, 27, 35, 10 };
        Bubble_sort(list);
        // 输出已排好序的序列
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}

如下为用冒泡排序算法对 {14,33,27,35,10} 进行升序排序的 Python 程序：

#待排序序列
list = [14,33,27,35,10]
def Bubble_sort():
    #有多少个元素，就遍历多少遍
    for i in range(len(list)):
        #从第 1 个元素开始遍历，比那里至 len(list)-1-i
        for j in range(len(list)-1-i):
            #比较两个相邻元素的大小
            if list[j] > list[j+1]:
                #交换 2 个元素的位置
                list[j],list[j+1] = list[j+1],list[j]

Bubble_sort()
for i in list:
    print(i,end=" ")

以上程序的执行结果均为：

10 14 27 33 35