qidao123.com ToB IT社区-企服评测·应用市场

标题: C++实现排序算法：冒泡排序 [打印本页]

---

作者: 立聪堂德州十三局店    时间: 2024-12-8 15:23
标题: C++实现排序算法：冒泡排序
目次
前言
冒泡排序性质
C++代码实现冒泡排序
冒泡图解
第一趟排序
第二趟排序
第三趟排序
排序结果
结语

---

前言
        冒泡排序的根本思想是通过从前往后（从后往前）两两比较，若为逆序（即arr < arr[i + 1]）则交换。整个排序方式像是在水底泡泡往上浮。本文会给出冒泡排序的C++实现，并辅以图形解释冒泡排序的过程。
冒泡排序性质

排序	时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n^2)	O(1)	否

C++代码实现冒泡排序

   冒泡排序C++实现

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. void Print(vector<int> &arr)
7. {
8.     for (auto v : arr)
9.     {
10.         cout << v << ' ';
11.     }
12.     cout << endl;
13. }
15. int main()
16. {
17.     // arr待排序的vector对象。这里以将arr最终调整为升序为例
18.     vector<int> arr{9, 1, 6, 7, 6};
20.     for (int i = 0; i < arr.size(); i++)
21.     {
22.         // flag 为一个标志, 如果有一趟没有进行数据交换,
23.         // 则该序列已经为有序序列, 可以提前跳出循环, 完成排序
24.         bool flag = false;
25.         for (int j = 0; j < arr.size() - 1 - i; j++)
26.         {
27.             if (arr[j] > arr[j + 1])
28.             {
29.                 // 满足条件 进行元素交换
30.                 std::swap(arr[j], arr[j + 1]);
31.                 // 修改标志位，证明本趟排序中发生过元素交换
32.                 flag = true;
33.             }
34.         }
35.         // 判断这次比较过程中是否进行交换，
36.         // 如果没有进行交换则待排序序列已经为有序序列。就可以提前跳出循环。
37.         if (!flag)
38.         {
39.             break;
40.         }
41.     }
42.     // 输出排序后的结果。
43.     Print(arr);
44.     return 0;
45. }

复制代码

运行结果
  

  冒泡图解

下标	0	1	2	3	4
初始序列	9	1	6	7	6

第一趟排序

留意：这里的一趟以一次完整的内层循环作为一趟，即在本趟排序中 i 值不变。
   

第一趟第一次比较	i == 0
	j == 0	j+1 == 1
	9	1	6	7	6
当前arr[j] > arr[j+1] 举行交换  j++ == 1
本次比较后交换结果	1	9	6	7	6

  

第一趟第二次比较	i == 0
		j == 1	j+1 == 2
	1	9	6	7	6
当前arr[j] > arr[j+1] 举行交换  j++ == 2
本次比较后交换结果	1	6	9	7	6

  

第一趟第三次比较	i == 0
			j == 2	j+1 == 3
	1	6	9	7	6
当前arr[j] > arr[j+1] 举行交换  j++ == 3
本次比较后交换结果	1	6	7	9	6

  

第一趟第四次比较	i == 0
				j == 3	j+1 == 4
	1	6	7	9	6
当前arr[j] > arr[j+1] 举行交换  j++ == 4
本次比较后交换结果	1	6	7	6	9

  

当前 j == 4 不满足进入循环条件 j < arr.size() - 1 - i 跳出内层循环, i++ = 2 进入第二趟排序.

          本趟排序中将 9 这个序列中最大的值，调解到最后一个位置。所以当前只有 前arr.size() - 1 - i个元素处于无序状态。
  第二趟排序

   

下标	0	1	2	3	4
第二趟初始序列	1	6	7	6	9

  

第一次比较		i == 1
	j == 0	j + 1 == 1
	1	6	7	6	9
当前arr[j] < arr[j+1] 不举行交换  j++ == 1
本次比较后交换结果	1	6	7	6	9

  

第二次比较		i == 1
		j == 1	j++ == 2
	1	6	7	6	9
当前arr[j] < arr[j+1] 不举行交换  j++ == 2
本次比较后交换结果	1	6	7	6	9

  

第三次比较
		i == 1
			j == 2	j++ == 3
	1	6	7	6	9
当前arr[j] > arr[j+1] 举行交换  j++ == 3
本次比较后交换结果	1	6	6	7	9

  

当前 j == 3 不满足进入循环条件j < arr.size() - 1 - i 跳出内层循环, i++ = 2 进入第三趟排序.

  第三趟排序

   

下标	0	1	2	3	4
第三趟初始序列	1	6	6	7	9

  

第三趟第一次比较			i == 2
	j == 0	j+1 == 1
	1	6	6	7	9
当前arr[j] < arr[j+1] 不举行交换  j++ == 1
本次比较后交换结果	1	6	6	7	9

  

第三趟第二次比较			i == 2
		j == 1	j+1 == 2
	1	6	6	7	9
当前arr[j] == arr[j+1] 不举行交换  j++ == 2
本次比较后交换结果	1	6	6	7	9

  

当前 j == 2 不满足进入循环条件j < arr.size() - 1 - i 跳出内层循环,  本次排序过程中没有举行一次数据交换(示例代码中的 flag 标志位 没有被改变), 所以该序列,已经是有序序列了. 所以提前跳出循环. 排序成功.

  排序结果

   最终排序结果：  

下标	0	1	2	3	4
初始序列	9	1	6	7	6
最终排序结果	1	6	6	7	9

        根据结果，可以发现初始序列中和最终结果中的    6   和     6   的相对位置并没有发生改变，所以  冒泡排序是稳定  的  结语

        希望本文对你有所帮助，谢谢点赞关注收藏。假如有什么问题，欢迎私信或者批评区讨论。

感谢阅读

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com ToB IT社区-企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.5