C++实现排序算法：冒泡排序

目录

前言

冒泡排序性质

C++代码实现冒泡排序

冒泡图解

第一趟排序

第二趟排序

第三趟排序

排序结果

结语

---

前言

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

冒泡排序性质

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

C++代码实现冒泡排序

冒泡排序C++实现

#include <iostream>
#include <vector>

using namespace std;

void Print(vector<int> &arr)
{
    for (auto v : arr)
    {
        cout << v << ' ';
    }
    cout << endl;
}

int main()
{
    // arr待排序的vector对象。这里以将arr最终调整为升序为例
    vector<int> arr{9, 1, 6, 7, 6};

    for (int i = 0; i < arr.size(); i++)
    {
        // flag 为一个标志, 如果有一趟没有进行数据交换,
        // 则该序列已经为有序序列, 可以提前跳出循环, 完成排序
        bool flag = false;
        for (int j = 0; j < arr.size() - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 满足条件 进行元素交换
                std::swap(arr[j], arr[j + 1]);
                // 修改标志位，证明本趟排序中发生过元素交换
                flag = true;
            }
        }
        // 判断这次比较过程中是否进行交换，
        // 如果没有进行交换则待排序序列已经为有序序列。就可以提前跳出循环。
        if (!flag)
        {
            break;
        }
    }
    // 输出排序后的结果。
    Print(arr);
    return 0;
}

运行结果

冒泡图解

下标	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 的相对位置并没有发生改变，所以 冒泡排序是稳定 的

结语

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

感谢阅读

原文地址：https://blog.csdn.net/qq_45730378/article/details/144172480

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！