冒泡排序#

冒泡排序原理#

原理：

比较两个相邻的元素，符合要求（看自己的需求是从小到大，还是从大到小）即交换两个元素的位置。

算法步骤#

比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。

交换位置：如果前一个元素比后一个元素大，则交换它们的位置。

重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被”冒泡”到列表的最后。

缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。

模拟过程#

假设有一个待排序的列表 [5, 3, 8, 4, 6]，冒泡排序的过程如下：

第一轮遍历：

比较 5 和 3，交换位置，列表变为 [3, 5, 8, 4, 6]。

比较 5 和 8，不交换。

比较 8 和 4，交换位置，列表变为 [3, 5, 4, 8, 6]。

比较 8 和 6，交换位置，列表变为 [3, 5, 4, 6, 8]。

第一轮结束后，最大的元素 8 已经”冒泡”到列表的最后。

第二轮遍历：

比较 3 和 5，不交换。

比较 5 和 4，交换位置，列表变为 [3, 4, 5, 6, 8]。

比较 5 和 6，不交换。

第二轮结束后，第二大的元素 6 已经”冒泡”到列表的倒数第二位置。

第三轮遍历：

比较 3 和 4，不交换。

比较 4 和 5，不交换。

第三轮结束后，列表已经有序。

第四轮遍历：

比较 3 和 4，不交换。

列表已经完全有序。

图解#

![[冒泡排序示意图.gif]]

coding#

对一个数组，排升序的冒泡排序代码

1
int a[N];
2
void solve()
3
{
4
    int n;cin>>n;
5
    for(int i=1;i<=n;i++)
6
    {
7
        cin>>a[i];
8
    }
9

10
    for(int i=1;i<=n;i++)//进行n轮
11
    {
12
        for(int j=1;j<=n-i;j++)//每一轮进行 n-i次
13
        {
14
            if(a[j]>a[j+1]) swap(a[j],a[j+1]);//判断语句
15
        }
16
    }
17
    for(int i=1;i<=n;i++)
18
    {
19
        cout<<a[i]<<" ";
20
    }
21
    cout<<'\n';
22
}

例题#

链接 https://www.luogu.com.cn/problem/P1271

![[Pasted image 20251108174527.png]]

2023 南阳理工新生赛 2024 郑州轻工业大学新生赛 2024 CCPC区域赛(郑州站) 2025 郑州轻工业大学校赛 2025 ICPC邀请赛(武汉) 2025 ICPC邀请赛(西安) 2025 ICPC河南省赛 2025 CCPC邀请赛或河南省赛 2025 CCPC邀请赛(福建) 2025 ICPC亚洲区域赛(西安站) 2025 ICPC亚洲区域赛(沈阳站)