跳转至

冒泡排序 (Ver. I)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换

输入

测试数据有多组，

每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。

输出

对于每组测试数据，

输出交换次数

样例输入

1
2
10
1 3 6 9 0 8 5 7 4 2

样例输出

1
22

提示

解决方案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>

int main() {
    int size;
    while (std::cin >> size) {
        std::vector<int> vector(static_cast<size_t>(size));
        for (int i = 0; i < size; ++i) {
            std::cin >> vector[i];
        }
        int count = 0;

        for (int i1 = 0; i1 < vector.size() - 1; ++i1) {
            for (int i2 = 0; i2 < vector.size() - 1 - i1; ++i2) {
                if (vector[i2] > vector[i2 + 1]) {
                    std::swap(vector[i2], vector[i2 + 1]);
                    count += 1;
                }
            }
        }
        std::cout << count << std::endl;
    }

    return 0;
}

评论