用C语言完成（洛谷# P1116 车厢重组）冒泡排序与仅统计逆序对

E3lct

723人浏览 · 2025-03-01 19:45:51

E3lct · 2025-03-01 19:45:51 发布

用C语言完成（洛谷 P1116 车厢重组）冒泡排序与仅统计逆序对

P1116 车厢重组

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数 $\le 10000)$ 。

第二行是 $N$ 个不同的数表示初始的车厢顺序。
（注：实际上数据中并不都在同一行，有可能分行输入）

输出格式

一个整数，最少的旋转次数。

输入输出样例 #1

输入 #1

4
4 3 2 1

输出 #1

题目链接

P1116 车厢重组 - 洛谷

代码实现-1（冒泡排序）

#include <stdio.h>

int main() {
    int n, list[10001], count = 0;           //list数组存入车厢，count存入调车次数
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {          
        scanf("%d", &list[i]);
    }

    // 冒泡排序核心：相邻元素比较并交换
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                // 交换相邻元素并计数
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
                count++; // 每次交换对应一次调车
            }
        }
    }
    printf("%d", count);
    return 0;
}

还有-2（逆序对）

#include <stdio.h>

int main()
{
    int n, list[10001] = {0}, count = 0;   //list数组存入车厢，count存入调车次数
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &list[i]);
    }
    for (int i = 0; i < n - 1; i++)        
    {
        for (int j = i + 1; j < n; j++)
        {
            if (list[i] > list[j])
            {
                count++;
            }
        }
    }
    printf("%d", count);
    return 0;
}

我的思路-1（冒泡）

确定

阅读题目，我们可以知道：

是相邻的车厢交换
从小到大排序
直接模拟调车过程，就很适合冒泡排序了，我们通过记录交换相邻元素的次数来统计调车次数

核心代码：

for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                // 交换相邻元素并计数
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
                count++; // 每次交换对应一次调车
            }
        }
    }

解释冒泡排序：

1.怎么冒泡?(举例排队)

想象你有一队随机排列的小朋友，要按照身高从矮到高排队。冒泡排序就像老师一遍遍地检查队列，让相邻的两个小朋友比较身高，如果左边的比右边高，就让他们交换位置。

像气泡从水底慢慢浮到水面一样，最大的数字（最高的小朋友）会逐渐“冒”到队列的末尾。

2.实现核心

假设队伍有5个小朋友，初始顺序是 [5, 3, 4, 1, 2]

1.`i`控制次数，在5个小朋友时，要循环4次即可排完

for (int i = 0; i < n - 1; i++)     //i从0开始，到n-2

2.`j`提供比较对象,比较相邻的两个数的大小,如果不符合要求，就交换，并且次数加一

if (list[j] > list[j + 1]) {
                // 交换相邻元素并计数
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
                count++; // 每次交换对应一次调车
            }

3.模拟：第一轮排序（i=0）

比较5和3 → 交换 → [3,5,4,1,2]（计数+1）
                 ↑j    
比较5和4 → 交换 → [3,4,5,1,2]（计数+1）
                   ↑j
比较5和1 → 交换 → [3,4,1,5,2]（计数+1）
                     ↑j
比较5和2 → 交换 → [3,4,1,2,5]（计数+1）
                       ↑j
                          ↑j+1

结果：最大的“5”到了最右边，计数共+4次。

4. 每一次`j`遍历完后（完成一次排序），内层循环（j）：负责相邻比较，范围随轮数增加而缩小（因为末尾已排序部分无需再比）。

第一次：(i=0) 排序j个

j<n-0-1;

第二次：(i=1) 经过第1轮排序,最后1个已经是最大的了的,只用排序j-1个

j<n-1-1;

…
第i次：(i) 经过第i轮排序,最后i个已经是最大的了的,只用排序j-i个

j<n-i-1;

所以j的范围是

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

5.代码复现

for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                // 交换相邻元素并计数
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
                count++; // 每次交换对应一次调车
            }
        }
    }

这便是

我的思路-2（逆序对）

确定

首先是阅读题目，我们可以知道：

是相邻的车厢交换
从小到大排序
那我们就可以统计逆序对，不是进行实际的元素交换排序（冒泡排序）
ps:我一开始以为这个是冒泡，但好像不是

核心代码

for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(list[i]>list[j])
            {
                count++;
            }
        }
    }

与冒泡排序的区别：

冒泡排序：

通过 相邻元素交换 逐步将最大值移至末尾，时间复杂度 O(n²) 且会修改数组

此代码：

仅 遍历所有元素对 统计逆序对，时间复杂度 O(n²) 但 不修改数组

解释-1：i与j的范围

外层循环 `i < n-1` 的原因：

当 i = n-2 时，j = i+1 = n-1，此时比较的是数组中最后两个元素
若 i 允许到 n-1，则 j = i+1 = n 会越界

内层循环 `j < n` 的原因：

对于每个 i，需要比较其与 所有右侧元素（即 i+1 到 n-1）

图示意：

1  2  3  4  5  6
            ↑i(这里是n-2的位置，也是i能到达最远的位置,i<n-1)
               ↑j(这里是n-1的位置，也是j能到达最远的位置,j<n)

解释-2：为何逆序数能反映最小调车次数？

核心逻辑：

每次相邻交换最多消除 1 个逆序对，且必须消除所有逆序对才能得到有序数组。

举例：

数组：[2, 1, 4, 3]
逆序对统计：
- 2>1
- 4>3
  总计 2 个逆序对。
实际交换过程：
1. [2,1,4,3] → [1,2,4,3]（消除 2>1）
2. [1,2,4,3] → [1,2,3,4]（消除 4>3）
  总计 2 次交换，与逆序对数一致。

记忆的模板

冒泡排序

for (int i = 0; i < n - 1; i++)             
{
    for (int j = 0; j < n - i - 1; j++)  //注意j的范围，这里是j<n-i-1
    {
        if (arr[j] > arr[j + 1])
        {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}