前言
本文介绍一种经典排序算法——冒泡排序，是入门级的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。
一、冒泡排序简介
冒泡排序法又称为交换排序法，从第一个元素开始，比较相邻元素的大小，若大小有误，则对调后再进行下一个元素的比较，就像是气泡从水底一点点冒出一样。如此扫描一次可确保最后一个元素位于正确的顺序，接下来再进行第二次扫描，将次大的值放在倒数第二个位置，以此类推，直到完成所有元素的排序。
二、算法特点
1）n个元素冒泡排序法最多执行n-1次扫描。最坏情况和平均情况需执行(n-1)+(n-2)+....+3+2+1=n(n-1)/2次，时间复杂度为O(n2)；最好情况只需扫描一次即可，也就是本身已经排序好了，这样只执行了n-1次，时间复杂度为O(n)。
2）由于冒泡为相邻两个数据相互比较而后决定是否互换位置，并不会改变原来排序的顺序，因此属于稳定排序法。
3）只需要一个额外空间，空间复杂度很低。
4）此排序法适用于数据量小或有部分数据已经排序过的情况。
三、代码实现
// 冒泡排序 vector<int> BubbleSort(vector<int> data) { // 拷贝 vector<int> result = data; // 排序过程：最多扫描n-1次，n为数据个数 int size = static_cast<int>(data.size()); for (int t = size - 1; t >= 0; --t) { // 若已排序好，扫描一遍后，flag应为false，此时可中断以达到提速效果 bool flag = false; for (int i = 0; i < t; ++i) { if (result[i] > result[i + 1]) { int temp = result[i]; result[i] = result[i + 1]; result[i + 1] = temp; flag = true; } } if (!flag) break; } return result; }
四、C++示例
#include <iostream> #include <iomanip> #include <vector> #include <string> using namespace std; // 展示当前顺序 void Show(vector<int> data) { size_t size = data.size(); for (size_t i = 0; i < size; ++i) cout << setw(4) << data[i]; cout << endl; } // 冒泡排序 vector<int> BubbleSort(vector<int> data) { // 拷贝 vector<int> result = data; cout << "冒泡排序：\n原始数据：\n"; Show(result); // 排序过程：最多扫描n-1次，n为数据个数 int size = static_cast<int>(data.size()); for (int t = size - 1; t >= 0; --t) { // 若已排序好，扫描一遍后，flag应为false，此时可中断以达到提速效果 bool flag = false; for (int i = 0; i < t; ++i) { if (result[i] > result[i + 1]) { int temp = result[i]; result[i] = result[i + 1]; result[i + 1] = temp; flag = true; } } if (!flag) break; cout << "第" << size - t << "次排序结果：\n"; Show(result); } cout << "排序后结果：\n"; Show(result); return result; } // 主函数 int main() { vector<int> data = { 9,11,567,0,-2,4,2 }; // 冒泡排序 vector<int> result1 = BubbleSort(data); system("pause"); return 0; }
效果图：
综上所述，冒泡排序法是个比较基础的排序法，优点是便于理解和稳定，缺点就是挺慢的，工程上还是用别的算法吧~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
