前言

相信你们已经见过不少好的排序算法，例如 Bogo 排序、Miracle 排序等。但是你见过好的排序，同时真的可以 AC 题目吗？这就是极好的排序算法。

取随机数 + 取毫秒

下面的算法会用到。

#include <random>
#include <chrono>

int getms()
{ // 得到当前毫秒
    auto now = std::chrono::system_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(
        now.time_since_epoch()
    );
    return ms.count();
}

int randint(int l, int r)
{ // 得到 [l, r] 的随机整数
    static std::mt19937 gen(static_cast<unsigned>(
        std::chrono::steady_clock::now().time_since_epoch().count()
    ));
    std::uniform_int_distribution<int> dist(l, r);
    return dist(gen);
}

一些好的排序算法

Bogo 排序

Bogo 排序，俗称猴子排序。步骤：

  1. 检查数组是否有序。
    • 如果有序，退出。
    • 如果无序，继续进行。
  2. 随机打乱数组。

代码可参考：

#include <iostream>
#define int long long
using namespace std;

int getms();
int randint(int l, int r);

const int N = 1e5 + 5;
int n, a[N];

bool check()
{ // 检查是否有序
	for (int i = 1; i < n; ++i)
		if (a[i] > a[i + 1])return 0;
	return 1;
}

void randa()
{ // 随机打乱数组
	for (int i = 1; i <= n; ++i)
		swap(a[i], a[randint(1, n)]);
}

void bsort()
{ // 核心代码
	while (!check())
		randa();
}

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	bsort();
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

时间复杂度：

  • 最优：O(n)O(n)。第一次检查就是好的。
  • 期望：O(n×n!)O(n\times n!)。nn 个数就有 n!n! 个排列，乘上每次检查就是了。
  • 最差：O(∞)O(\infty)。一直都没有好。

空间复杂度：

  • O(1)O(1)。这里的空间复杂度是指除开原数组之外的空间。就像归并排序的空间是 O(n)O(n)。

Miracle 排序

Miracle 排序，俗称奇迹排序。步骤：

  1. 检查数组是否有序。
    • 如果有序，退出。
    • 如果无序，继续进行。
  2. 等待宇宙射线/量子涨落/神迹把数组变成有序。

代码可参考：

#include <iostream>
#define int long long
using namespace std;

int getms();
int randint(int l, int r);

const int N = 1e5 + 5;
int n, a[N];

bool check()
{ // 检查
	for (int i = 1; i < n; ++i)
		if (a[i] > a[i + 1])return 0;
	return 1;
}

void wait() { return ; } // 等待

void Msort() // M 大写是因为和归并排序冲突了
{ // 核心代码
	while (!check())
		wait();
}

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	Msort();
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

时间复杂度：

  • 最优：O(n)O(n)。原来就有序，检查一次就好了。
  • 期望/最差：O(∞)O(\infty)。一直等。

空间复杂度：

  • O(1)O(1)。没有多余的数组开销。

DeepSleep 排序

DeepSleep 排序，俗称睡眠排序。步骤：

  1. 为每个数字建立线程。
  2. 线程休眠 数字×单位时间数字 \times 单位时间 毫秒。
  3. 每个线程结束输出当前数字。
  4. 直到所有线程结束。

朴素 DeepSleep 排序：

#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, m, a[N], b[N];

void deep_sleep(int num) 
{
    // 休眠 num * 10 毫秒，数字越大醒得越晚
    this_thread::sleep_for(chrono::milliseconds(num * 10));
    b[++m] = num; // 新开一个数组，避免占用原数组 
}

void DSort()
{ // 核心代码 
	vector <thread> threads;
    // 1. 为每个数字创建线程
    for (int i = 1; i <= n; ++i) 
        threads.emplace_back(deep_sleep, a[i]);
    
    // 2. 等待所有线程结束（join）
    for (auto &t : threads) 
        t.join();
}

signed main() 
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
    
	DSort();
	
	for (int i = 1; i <= m; ++i)
		cout << b[i] << ' ';
    return 0;
}

时间复杂度：

  • O(max⁡(a)×t)O(\max(a)\times t)，tt 为单位时间。

空间复杂度：

  • O(n)O(n)。新开数组避免占用原来的数组。

但是，这样做有一个致命的问题！（怎么一股 AI 味）

就是：

  1. 不能处理非正数和小数。
  2. 数字大（10910^9）时等 101010^{10} 秒，就是 115115 天。

就是这样了。所以我们要引入优化。

  1. 对于不能处理非正数：这个简单，我们在处理之前对所有数进行平移，具体就是每个数都加上一个数使得每个数都变为正数。这样不会改变数据之间的大小关系。
  2. 对于数字大：可以使用一些数据结构常用的方法：离散化。具体的：给每个数字一个排名，用这个排名代替原来的数字。这样就将原来有 10910^9 的数据映射到 10510^5（数组长度上界）。

优化睡眠排序：

#include <algorithm>
#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include <mutex>
#include <set>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, m, o, a[N], b[N], c[N];
mutex mtx;

void deep_sleep(int num) 
{
    // 休眠 num * 10 毫秒，数字越大醒得越晚
    this_thread::sleep_for(chrono::milliseconds(num * 10));
    lock_guard<mutex> lock(mtx);
    c[++o] = num; // 新开一个数组，避免占用原数组 
}

void DSort()
{ // 核心代码 
	vector <thread> threads;
    // 1. 为每个数字创建线程
    for (int i = 1; i <= n; ++i) 
        threads.emplace_back(deep_sleep, a[i]);
    
    // 2. 等待所有线程结束（join）
    for (auto &t : threads) 
        t.join();
}

void ls()
{ // 离散化 
	set <int> s; // 使用 set 创建排名 
	for (int i = 1; i <= n; ++i) s.insert(a[i]);
	for (int it : s) b[++m] = it;
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}

signed main() 
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	ls(); // 离散化（过程自动平移） 
    
	DSort();
	
	for (int i = 1; i <= n; ++i)
		cout << b[c[i]] << ' '; // 记得还原到原数组 
    return 0;
}

时间复杂度：

  • O(nt)O(nt)，tt 为单位时间。

空间复杂度：

  • O(n)O(n)。实际上常数更大。

其实吧，set 内部红黑树就能自动排序。而且你别想在洛谷上交这份代码，满屏 RE 够你受的。

Stalin 排序

不必多说了吧，，，😱

步骤：维护一个当前最大值，没有超过的直接删除。

代码可参考：

#include <iostream>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, a[N], m, b[N];

void ssort()
{
	int mmx = a[1]; // 当前最大值
	for (int i = 1; i <= n; ++i)
	{
		if (a[i] >= mmx)
		{
			b[++m] = a[i];
			mmx = a[i];
		}
	}
}

signed main() 
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
    ssort();
	
	for (int i = 1; i <= m; ++i)
		cout << b[i] << ' '; // SXXX 排序不一定会得到 n 个数字的 
    return 0;
}

时间复杂度：

  • O(n)O(n)。😱吓哭了最强排序，，，。

空间复杂度：

  • O(n)O(n)。保留的数据。如果要直接在原数组删除，空间可以达到 O(1)O(1)，但时间会变成 O(n2)O(n^2)。

不过这样也太血腥暴力了。为何不多保留一些人呢？我们还是可以维护 bb 表示留下的人。每个人进来时，二分查找最后一个比自己小的，然后代替他。如果没有，则直接加到 bb 的末尾。

代码可参考：

#include <algorithm>
#include <iostream>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, a[N], m, b[N];

void ssort()
{
	for (int i = 1; i <= n; ++i)
	{
		if (a[i] > b[m]) b[++m] = a[i]; // 没有更小的了，加入末尾
		else b[lower_bound(b + 1, b + m + 1, a[i]) - b] = a[i]; // 找到最后一个比自己小的
	}
}

signed main() 
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
    ssort();
	
	for (int i = 1; i <= m; ++i)
		cout << b[i] << ' '; // SXXX 排序不一定会得到 n 个数字的 
    return 0;
}

时间复杂度：

  • O(nlog⁡n)O(n \log n)。遍历 nn，二分 log⁡n\log n。

空间复杂度：

  • O(n)O(n)。

等等，，这不就是 LIS 的 贪心 + 二分，O(nlog⁡n)O(n \log n) 实现吗？？

正文

前置知识：插入排序

用扑克牌比喻。假设你现在有一些从小到大排好序的牌。

  1. 现在你拿到了一张新的牌，记为「新牌」。
  2. 从后往前，直到当前牌比新牌小。
  3. 将新牌插入到当前牌的后面。

这就是插入排序了。代码：

#include <iostream>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, a[N];

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	// 插入排序 
	for (int i = 2; i <= n; i++) 
	{
	    int key = a[i], j = i - 1;
	    while (j >= 1 && a[j] > key) 
		{  // 每次执行 = 消除 1 个逆序对
	        a[j + 1] = a[j];
	        j--;
	    }
	    a[j + 1] = key;
	}
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

可以发现，这和冒泡排序、归并排序一样可以求逆序对 插入排序的时间复杂度，很大程度上是决定于逆序对的数量。所以如果能减少逆序对数量，那就能优化插入排序！（又有一股 AI 味了）

附加知识：希尔排序

可跳过。

根据上面的 ↑ 内容，通过减少逆序对，就能对插入排序优化。这就是希尔排序。步骤：

  1. 先大步长地比较和交换，消除远距离的逆序对。
  2. 逐步缩小步长，直到步长为 1（此时就是普通插入排序）。
  3. 经过前面的“预处理”，逆序对数量已经大幅减少，最后的插入排序就非常快。

部分代码（DeepSeek 提供）：

void shell_sort(int a[], int n) {
    // 步长从 n/2 开始，逐步减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列做插入排序
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i;
            // 比较相隔 gap 的元素
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

但是我这里毕竟不是为了将希尔排序，所以不详细将了。

随机打乱 + 插入排序

这就是本篇 blog 的主要内容了。

随机打乱

一个由 Bogo 猴子排序引出的想法：每次都打乱所有数字也太慢了，不如每次随机交换数字，而且交换前判断这样做是否能使数组更有序而不是更乱。代码：

#include <iostream>
#include <random>
#include <chrono>
#define int long long
using namespace std;

int getms();
int randint(int l, int r);

const int N = 1e5 + 5;
int n, a[N], st;

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
		
	int st = getms(); // 开始打乱时间 
	while (getms() - st < 990)
	{ // 持续打乱 990ms，避免超时 
		int i = randint(1, n - 1);
		int j = randint(i + 1, n);
		if (a[j] < a[i])
			swap(a[i], a[j]);
	}
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

交上洛谷之后：TLE ✕ 3。那缩短时间呢，改成打乱 900ms 呢？WA ✕ 3。于是就要引出插入排序了。

混合

如果逆序对较少，插入排序是很高效的。经过随机打乱，肯定已经解决了部分（至少是小部分）逆序对。因此，打乱后再做插入排序。这样就好了。

代码：

#include <iostream>
#include <random>
#include <chrono>
#define int long long
using namespace std;

int getms();
int randint(int l, int r);

const int N = 1e5 + 5;
int n, a[N], st;

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	// 随机减少逆序对 
	int st = getms();
	while (getms() - st < 900)
	{
		int i = randint(1, n - 1);
		int j = randint(i + 1, n);
		if (a[j] < a[i])
			swap(a[i], a[j]);
	}
	
	// 插入排序 
	for (int i = 2; i <= n; i++) 
	{
	    int key = a[i], j = i - 1;
	    while (j >= 1 && a[j] > key) 
		{  // 每次执行 = 消除1个逆序对
	        a[j + 1] = a[j];
	        j--;
	    }
	    a[j + 1] = key;
	}
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

交上洛谷，竟然 AC 了！我到底在惊讶什么，都做过插入排序了肯定 AC 啊。但是，纯插入排序是不能 AC 的。

时间复杂度：

  • 最优：O(再给我900ms的时间打乱吧)O(再给我 900ms 的时间打乱吧)。如果数组本来就有序，则无序做插入排序。只需要等 900900 毫秒。
  • 期望/最差：O(n2)O(n^2)。插入排序是 O(n2)O(n^2) 的。而且这个随机打乱其实就是“随机版冒泡排序”，理论上也是 O(n2)O(n^2)。

空间复杂度：O(1)O(1)。

可以优化：如果数组本来就有序，或者打乱的过程中接近有序，那么不需要再打乱了。称打乱失败为随机取数后这两个数有序。那么可以设定打乱失败次数超过一个阙值，则提前结束打乱。代码：

#include <iostream>
#include <random>
#include <chrono>
#define int long long
using namespace std;

int getms();
int randint(int l, int r);

const int N = 1e5 + 5;
int n, a[N], st, m, cnt;

signed main()
{
	cin >> n;
	m = n; // 最多可以忍受的打乱失败次数 
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	// 随机减少逆序对 
	int st = getms();
	while (getms() - st < 900)
	{
		int i = randint(1, n - 1);
		int j = randint(i + 1, n);
		if (a[j] < a[i])
		{
			cnt = 0;
			swap(a[i], a[j]);
		}
		else
		{
			++cnt;
			if (cnt > m) break;
		}
	}
	
	// 插入排序 
	for (int i = 2; i <= n; i++) 
	{
	    int key = a[i], j = i - 1;
	    while (j >= 1 && a[j] > key) 
		{  // 每次执行 = 消除1个逆序对
	        a[j + 1] = a[j];
	        j--;
	    }
	    a[j + 1] = key;
	}
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << ' ';
	return 0;
}

这样，可以得到一点优化。当然，打乱和插入排序可以做一些权衡。500ms~600ms 是比较好的选择。900ms 中，可能前一部分是很有效的，后一部分时数组已经接近有序，此时做插入排序就很快。

然而经过测试，发现一个问题：这个随机化过程中，如果 n=1n=1 会炸。特判一下就好了。

  1. Language
  2. 兼容模式
  3. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 14ms
  5. Powered by Hydro v5.0.7 Community