全比排序（自己创造的）

· · 个人记录

全比排序

思想

全比排序的思想就是拿每个数去跟它后面的数字交换，例如 [2, 4, 1, 3] 的排序是这样的。

[2],[4], 1, 3(2 < 4) \gets 2, 4, 1, 3 [2], 4, [1], 3(2 > 1) \gets 1, 4, 2, 3 [1], 4, 2, [3](1 < 3) \gets 1, 4, 2, 3 1, [4], [2], 3(4 > 2) \gets 1, 2, 4, 3 1, [2], 4, [3](2 < 3) \gets 1, 2, 4, 3 1, 2, [4], [3](4 > 3) \gets 1, 2, 3, 4

这个排序跑不满 O(n^{2})，他的时间复杂度是 O\big(\dfrac{n^{2} - n}{2}\big)。对比一下，n = 12 时，冒泡排序为 O(12^{2}) = O(144)，全比排序为 O\big(\dfrac{12^{2} - 12}{2}) = O(66)，这个排序也算是比较好的。

\text{code}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 114514;
int n, a[N];

signed main() 
{
    qwq;
    cin >> n;
    for (int i = 1; i <= n; ++ i)//输入 
        cin >> a[i];
    for (int i = 1; i <= n; ++ i)//从 1 比到 n 
        for (int j = i + 1; j <= n; ++ j)//找 a[i] 后面的比 
            if (a[i] > a[j])
                swap(a[i], a[j]);//int temp = a[i], a[i] = a[j], a[j] = temp;
    for (int i = 1; i <= n; ++ i)//输出 
        cout << a[i] << " ";
    return 0;
}