P1177 【模板】排序

· · 题解

\text{P1177} 【模板】排序

前言

20 分做法：选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素（也就是 a_{i\cdots n} 中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。

选择排序具有不稳定的特点，最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n^2)。

由于这种做法复杂度太高，且用起来太差劲，直接贴上代码，仅供参考：

#include <bits/stdc++.h>
using namespace std;
template<typename T> //这里没什么用的快读
inline void read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();

    while (!isdigit(c)) {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }

    x *= f;
}
template<typename T, typename ... Args>
inline void read(T &x, Args &... y) {
    read(x);
    read(y...);
}
int n, a[100010];
signed main() {
    read(n);

    for (int i = 1; i <= n; i++)
        read(a[i]);

    for (int i = 1; i < n; i++) {
        int ith = i;

        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[ith])
                ith = j;
        }

        swap(a[i], a[ith]);
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';

    return 0;
}

60 分做法：冒泡排序、桶排序

冒泡排序

冒泡排序是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。可以证明，冒泡排序最多需要扫描 n-1 遍数组就能完成排序。

冒泡排序是一种稳定的排序算法,平均时间复杂度为 O(n^2)。代码如下：

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();

    while (!isdigit(c)) {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }

    x *= f;
}
template<typename T, typename ... Args>
inline void read(T &x, Args &... y) {
    read(x);
    read(y...);
}
int n, a[100010];
signed main() {
    read(n);

    for (int i = 1; i <= n; i++)
        read(a[i]);

    bool flag = true;

    while (flag) { // 还未满足有序
        flag = false;

        for (int i = 1; i < n; i++) {
            if (a[i] > a[i + 1]) {
                flag = true; // 交换后需要继续排序过程
                swap(a[i], a[i + 1]); // 交换两个元素
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';

    return 0;
}

计数排序

友情提示：本部分我采用了 STL 中的 map 实现，请不懂 map 的同学到下面去看正解。

\text{P1271} 【深基 9.例 1】选举学生会 一题中已经对其方法做了介绍，这里略过。放上代码：（MLE 2 个测试点）

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();

    while (!isdigit(c)) {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }

    x *= f;
}
template<typename T, typename ... Args>
inline void read(T &x, Args &... y) {
    read(x);
    read(y...);
}
map <int, int> t;
int n, a, maxi = -1;
signed main() {
    read(n);

    for (int i = 1; i <= n; i++) {
        read(a);
        t[a]++;
        maxi = max(maxi, a); // 取数列最大值，这样遍历 map 时可以减少时间
    }

    for (int i = 1; i <= maxi; i++) {
        for (int j = 1; j <= t[i]; j++)
            cout << i << ' ';
    }

    return 0;
}

正解：sort 排序

代码如下：

//P1177 【模板】快速排序
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';

    return 0;
}

引用