C++排序算法之冒泡排序

男娘i 2022-06-12 02:16 192阅读 0赞

**冒泡排序**

思想：通过一系列的“交换”动作完成。首先第一个记录和第二个记录比较，如果第一个大，则二者交换，否则不交换；然后第二个记录和第三个记录比较，如果第二个大，则二者交换，否则不交换..........一直按这种方式进行下去，最终最大的那个记录被交换到了最后，一趟冒泡排序完成。这个过程中，大的记录像一块石头一样“沉底”，小的记录逐渐向上“浮动”，冒泡排序的名字由此而来。

例如：3 6 4 2 1 8 5 7

下面进行第一趟冒泡排序：假设数组下标从0开始

（1） 0号和1号比较，3<6，不交换

结果：3 6 4 2 1 8 5 7

（2） 1号和2号比较，6>4，交换

结果：3 4 6 2 1 8 5 7

（3） 2号和3号比较，6>2，交换

结果：3 4 2 6 1 8 5 7

（4） 3号和4号比较，6>1，交换

结果：3 4 2 1 6 8 5 7

（5） 4号和5号比较，6<8，不交换

结果：3 4 2 1 6 8 5 7

（6） 5号和6号比较，8>5，交换

结果：3 4 2 1 6 5 8 7

（7） 6号和7号比较，8>7，交换

结果：3 4 2 1 6 5 7 8

一趟冒泡排序，最大的8被交换到了最后，8到达了它最后的位置。接下来按照同样的方法进行第二趟冒泡排序。经过若干趟后，最终序列有序。**注意，冒泡排序算法结束的条件是在一趟排序过程中没有发生元素交换**。

#include <iostream>
    #include <vector>
    using namespace std;
    
    //冒泡排序法，时间复杂度最坏O(n*n)，最好O(n)，平均时间复杂度为O(n*n)；空间复杂度为O(1)
    void BubbleSort(vector<int> &R)
    {
    	int flag,temp;                                  //变量flag用来记录本趟排序是否发生了交换
    	for (int i = R.size() - 1; i > 0; i--)
    	{
    		flag = 0;
    		for (int j = 0; j < i; j++)              //本循环找出待排队列中最大的数往后移
    		{
    			if (R[j] > R[j + 1])     
    			{
    				temp = R[j];
    				R[j] = R[j + 1];
    				R[j + 1] = temp;
    				flag = 1;
    			}
    		}
    		if (flag == 0)                           //一趟排序过程中没有发生元素交换，证明序列有序，排序结束
    			return;
    	}
    }
    
    void main()
    {
    	vector<int> R = { 3, 6, 4, 2,1,8,5,7 };
    	BubbleSort(R);
    	for (auto x: R)
    		cout << x << " ";
    	cout << endl;
    }

输出结果：

![Image 1][]![Center][]

**复杂度分析：**

**（1）时间复杂度：**

*  **最坏情况**，待排序列逆序，此时对于外层循环的每次执行，内层循环中if语句的条件R\[j\]>R\[j+1\]始终成立，即基本操作执行的次数为n-i。i的取值为1~n-1。因此基本操作总的执行次数为(n-1+1)(n-1)/2 = n(n-1)/2。由此可知时间复杂度为**O(n^2)**
 *  **最好情况**，待排序列有序，此时内层循环中if语句的条件始终不成立，交换不发生，且内层循环执行n-1次后这个算法结束，因此时间复杂度为**O(n)**。
 *  综合以上两种情况，平均情况下的时间复杂度为O(n^2)

**（2）空间复杂度**

需要额外辅助空间只有一个temp，因此空间复杂度为O(1)。

[Image 1]: 
[Center]: /images/20220612/69899fb57c2e41be92be0e39af715fc9.png