题解 | 【模板】排序

C++ 冒泡排序、选择排序时间复杂度为O(n^2)，快速排序、归并排序时间复杂度为O(nlogn)

#include <any>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void BubbleSort(vector<int> &a) {
    // 冒泡排序 -- O(n^2) -- 超时
    for (int i=0; i<a.size(); i++) {
        for (int j=0; j<a.size()-1-i; j++) {
            if (a[j] > a[j+1]) {
                int t = a[j+1];
                a[j+1] = a[j];
                a[j] = t;
            }
        }
    }
}

int Partition(vector<int> &a, int low, int high) {
    int p=a[low];
    int i=low+1, j=high;
    while (true) {
        while (i<=j && a[i]<=p) i++;
        while (i<=j && a[j]>p) j--;
        if (i>j) break;
        swap(a[i], a[j]);
    }
    swap(a[low], a[j]);
    return j;
}
void QuickSort(vector<int> &a, int low, int high) {
    // 快排 -- O(nlogn)
    if (low>=high) return;
    int idx = Partition(a, low, high);
    QuickSort(a, low, idx-1);
    QuickSort(a, idx+1, high);
}

int main() {
    int n;
    vector<int> a;
    cin >> n;
    while (n--) {
        int t;
        cin >> t;
        a.push_back(t);
    }
    // BubbleSort(a);
    QuickSort(a, 0, a.size()-1);
    for (auto i : a) {
        cout << i << ' ';
    }
}
// 64 位输出请用 printf("%lld")