冒泡排序解释：

冒泡排序 BubbleSort 是一种最基础的交换排序。顾名思义，数组中的每一个元素就好像泡泡一样，根据自己的大小不同一点点的向一侧移动。

冒泡排序原理：

每一趟只能确定将一个数归位。第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。

而 “每一趟” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

形象地说，冒泡排序就是每次都将当前最大的泡泡移动到最底下，此时这个当前最大的泡泡就完成了归位。之后再重复这样的操作。

冒泡排序动态演示：

以当前图中的几个数字为例，即 [1, 2, 5, 3, 4, 2]，进行冒泡排序的动态演示。

时间复杂度：

核心代码：

void BubbleSort(vector<int> &v){

    int n = v.size();

    for(int i = 0; i < n - 1; i++){

	for(int j = 0; j < n - 1 - i; j++){

	    if(v[j] > v[j + 1]){

		swap(v[j], v[j + 1]);

	    }

	}

    }

}

代码优化:

在上面的动态演示中，我们发现后面两趟比较并没有发生任何交换操作，而且此时数组已经有序。

那么有什么样的办法可以 避免这种时间上的浪费 呢？

所以我们可以定义一个 bool 变量 flag 来判断当前是否发生了交换操作，即判断当前是否有序。

若已经发现某一趟比较中没有任何交换操作，那么当前数组已经有序，可以提前退出。

核心代码(优化版本)：

void BubbleSort(vector<int> &v){

    int n = v.size();

    for(int i = 0; i < n - 1; i++){

	bool isSorted = true;    //记录当前一趟比较是否发生了交换

        for(int j = 0; j < n - 1 - i; j++){

            if(v[j] > v[j + 1]){

		isSorted = false;

		swap(v[j], v[j + 1]);

            }

	}

        if(isSorted) break;   //若当前一趟未发生交换，则已经有序，可以提前结束

    }

}

完整程序源代码：

#include<iostream>

#include<vector>

#include<ctime>

using namespace std;

void BubbleSort(vector<int> &v){

    int n = v.size();

    for(int i = 0; i < n - 1; i++){

	bool isSorted = true;    //记录当前一趟比较是否发生了交换

	for(int j = 0; j < n - 1 - i; j++){

	    if(v[j] > v[j + 1]){

	        isSorted = false;

	        swap(v[j], v[j + 1]);

	    }

        }

        if(isSorted) break;    //若当前一趟未发生交换，则已经有序，可以提前结束

    }

}

void show(vector<int> &v){

    for(auto &x : v)

	cout<<x<<" ";

    cout<<endl;

}

main(){

    vector<int> v;

    srand((int)time(0));

    int n = 50;          //随机生成50个数字

    while(n--)

	v.push_back(rand() % 100 + 1);  //数字范围[1, 100]

    show(v);

    BubbleSort(v);

    cout<<endl<<endl;

    show(v);

}

巴特西

[排序算法] 冒泡排序 (C++)