每日一题-13th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1271. 选举学生会

题干

学校正在选举学生会成员，有 n（n ≤ 999）名候选人，每名候选人编号分别从 1 到 n，现在收集到了 m（m ≤ 2000000）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

说明

输入格式

输入 n 和 m 以及 m 个选票上的数字。

输出格式

求出排序后的选票编号。

样例输入

1 2	5 10 2 5 2 2 5 2 2 2 1 2

样例输出

1	1 2 2 2 2 2 2 2 5 5

思路

普通的排序问题，拿这个练手；不过以洛谷的性格，普通 $O(n^2)$ 估计不太行；

实现

先拿直接插入排序试试水：

#include <iostream>
using namespace std;

int main() {
    int n, m, j;
    cin >> n >> m;
    int* arr = new int[m] {0};
    cin >> arr[0];
    for (int i = 1; i < m; ++i) {
        int tmp; cin >> tmp;
        j = i - 1;
        while (1) {
            if (arr[j] < tmp || j < 0) { arr[j + 1] = tmp; break; }
            else arr[j + 1] = arr[j];
            --j;
        }
    }
    for (int i = 0; i < m; ++i) cout << arr[i] << ' ';
    delete[] arr;
    return 0;
}

再用快速排序试试：

#include <iostream>
using namespace std;

int divide(int* arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (arr[right] > pivot && left < right) --right;
        if (left < right) arr[left] = arr[right];
        while (arr[left] <= pivot && left < right) ++left;
        if (left < right) arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void quickSort(int* arr, int left, int right) {
    if (left >= right) return;
    int mid = divide(arr, left, right);
    quickSort(arr, left, mid - 1);
    quickSort(arr, mid + 1, right);
}

int main() {
    int n, m;
    cin >> n >> m;
    int* arr = new int[m] {0};
    for (int i = 0; i < m; ++i) cin >> arr[i];
    quickSort(arr, 0, m - 1);
    for (int i = 0; i < m; ++i) cout << arr[i] << ' ';
    delete[] arr;
    return 0;
}

再用堆排序试试：

#include <iostream>
using namespace std;

// 大顶堆向下过滤
void percolateDown(int* arr, int idx, int size) {
    int next = 2 * idx + 1, tmp = arr[idx];
    while (1) {
        if (next + 1 < size && arr[next] < arr[next + 1]) ++next;
        if (next >= size || tmp >= arr[next]) { arr[idx] = tmp; break; }
        arr[idx] = arr[next];
        idx = next; next = 2 * idx + 1;
    }
}

void heapSort(int* arr, int size) {
    for (int i = (size - 1) / 2; i >= 0; --i)
        percolateDown(arr, i, size);
    for (int i = 0; i < size - 1; ++i) {
        int tmp = arr[0];
        arr[0] = arr[size - i - 1];
        arr[size - i - 1] = tmp;
        percolateDown(arr, 0, size - i - 1);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int* arr = new int[m] {0};
    for (int i = 0; i < m; ++i) cin >> arr[i];
    heapSort(arr, m);
    for (int i = 0; i < m; ++i) cout << arr[i] << ' ';
    delete[] arr;
    return 0;
}

然后发现都可以，，😂