算法介绍
冒泡排序是一种最基础的交换排序(两两比较待排序的关键字，交换不满足次序要求的那对数，直到整个表都满足次序要求为止)，工作方式如同碳酸饮料中的二氧化碳气泡最终会上浮到顶端一样，故名"冒泡排序"。
算法描述
一次比较相邻的数据，将小数据放在前(假设非递减排列)，大数据放在后。即第一趟比较第1个和第2个数，小数在前，大数在后，再比较第2个数与第3个数，小数在前，大数在后，以此类推比较第n - 1个和第n个数，小数在前，大数在后；第一趟后最大元素已放在正确位置，以此类推，直到全部元素放在正确的位置。
动图演示
算法分析
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
代码实现
// C++ void bubbleSort(int a[], int length) { // i表示这一趟要填入正确元素的位置，最后一个位置不需要比较 // 因为n-1个元素在正确位置，最后一个位置自然填入正确元素 for (int i = 0; i < length - 1; ++i) { // 从后往前依次比较，将最小元素"冒泡"到最前方，要填入正确元素的位置i for (int j = length - 1; j > i; --j) { // 交换不满足次序要求的元素 if (a[j] < a[j - 1]) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } }
算法优化
考虑一些特殊情况
1、待排序序列已经有序，整个代码任然会执行无效的遍历和比较。
2、数据已经排好序，但任然会进行下一轮比较，直到length-1次，后面的比较都是无意义的。
可以通过设置标志位flag，如果发生了交换就改变flag设置为true，如果没有交换就保持false。当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。退出循环，排序完成。
// C++ void bubbleSort2(int a[], int length) { bool flag = false; // 标记第i趟是否发生元素交换 // i表示这一趟要填入正确元素的位置，最后一个位置不需要比较 // 因为n-1个元素在正确位置，最后一个位置自然填入正确元素 for (int i = 0; i < length - 1; ++i) { flag = false; // 每趟默认未进行元素交换 // 从后往前依次比较，将最小元素"冒泡"到最前方，要填入正确元素的位置i for (int j = length - 1; j > i; --j) { if (a[j] < a[j - 1]) { // 交换不满足次序要求的元素 flag = true; // 发生元素交换，改变flag int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } if (flag == false) { // 未发生交换，序列满足要求，完成排序 break; // 跳出循环 } } }
参考
数据结构与算法分析(Java语言描述)
数据结构(C语言版)
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
