专栏文章

一种通过维护元素位置进行排序的方法

__ACGODs_
休闲·娱乐参与者 23已保存评论 22

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
20 条
当前快照
2 份
快照标识符
@mliagbp3
此快照首次捕获于
2026/02/12 01:13
上周
此快照最后确认于
2026/02/19 01:23
12 小时前
查看原文

一种通过维护元素位置进行排序的方法

这文章太垃圾了被转到休闲娱乐区了。

引子

我在看 cff 老师的游记时，看到了这样几句话：
在手动排序某些东西的时候突然想到“插入排序为什么不二分找插入的位置呢”，然后发现原来插入之后数组元素后移也需要时间复杂度。
如果比较所需的时间较多就需要这么做吧，应该。不对，那我也可以选其它排序。
不过手动排序的话二分插入排序还是挺方便的（
我们发现，插入排序的瓶颈在于“插入之后数组元素后移”。
那我们能否打破瓶颈呢？

思路

我们发现，每次插入一个元素，比这个元素大的元素都得后移。那我们能否抽象这个“后移”，使其时间复杂度降为 O(log⁡n)O(\log n) 或者更优呢（其实最后没有更优，希望后人在不在其他地方排序的前提下做到更优）？
作为一个做过一些题目的 OIer，我们可以发现：这个“后移”操作不正是把比这个数大的元素位置加一吗？
作为一个学过一些东西的 OIer，我们可以发现：这个“加一”操作是可以维护的，每次处理一个数就把这个数到一个很大很大的数（反正超过数组的最大值就行）的“位置”都加一。
居然都不用二分了。
具体（伪）代码：
PYTHON
# 我觉得用 Python 渲染效果好一些
# 但是这看起来像个缝合怪
for i in n:
  input(a[i]);
for i in n:
  for j in i~inf: # inf 为“很大很大的数”
    c[j]++; # c[j] 为维护的位置
for i in n:
  b[c[i]]=a[i];
for i in n:
  a[i]=b[i];
但是这个代码有好几个硬伤，我们一个一个处理。

复杂度依旧 O(n2)O(n^2)

这个“插入”依旧是时间复杂度瓶颈，但是我们发现这程序里要用到 cc 的地方无非就两处，所需要的操作也就只有区间修改和单点查询。
作为一个学过一些数据结构的 OIer，我们发现维护这个 cc 的数据结构需要满足以下几点：
  • 可以在比 O(n)O(n) 更优的时间复杂度下完成区间修改和单点查询。（这里可能不严谨，比 O(n)O(n) 更优的时间复杂度是指的时间复杂度高的那个操作）。
  • 或者可以在比 O(n)O(n) 更优的时间复杂度下完成单点修改和区间查询。（差分思想）。
  • 可以在比 O(n)O(n) 更优的时间复杂度下完成区间修改和区间查询。
  • 可以维护大的元素而不耗费大的内存（不能离散化，因为离散化要排序，除非你要写休闲娱乐文章）。
作为一个没学过多少数据结构的 OIer，我们只能想到动态开点线段树了。
代码上看，第二个要求好写点，所以就写第二个要求了。
具体（伪）代码：
PYTHON
for i in n:
  input(a[i]);
for i in n:
  add(a[i],inf,1); # a[i]~inf 加一
for i in n:
  b[query(0,a[i])]=a[i];
for i in n:
  a[i]=b[i];

不能处理元素有重复的情况

举个例子：a=[5,5,5,5]a=[5,5,5,5]，一通捣鼓之后 c=[0,0,0,5,… ]c=[0,0,0,5,\dots]，然后又是一通捣鼓之后，aa 就变成 [0,0,0,5][0,0,0,5] 了。
这很明显不对啊！
但是这个问题很好办，就是这样：
  1. 先把 bb 内的所有元素设为一个 aa 中永远用不上的值（例如 −inf-\text{inf}）。
  2. 再设一个缓存变量 ss。
  3. 从后往前修改（因为同一个元素会被统计多次，位置肯定会在常规方法排序后那个元素所在的最后一个位置），如果 bi=−infb_i=-\text{inf}，那么 bi=sb_i=s，否则 s=bis=b_i。
具体（伪）代码：
PYTHON
fill(b,-inf);
s=0;
for i in 1~n:
  input(a[i]);
for i in 1~n:
  add(a[i],inf,1); # a[i]~inf 加一
for i in 1~n:
  b[query(0,a[i])]=a[i];
for i in n~1:
  if(b[i]=-inf) b[i]=s;
  else s=b[i];
for i in n:
  a[i]=b[i];

无法处理负数

那这个就更简单了，给所有 aia_i 加上 inf\text{inf} 就行了。
当然还有这些地方要修改：
  1. cc 的大小翻倍。
  2. 最后 aia_i 要减 inf\text{inf}。
  3. 程序中还有些需要 inf\text{inf} 的地方需要变大，来达到 inf\text{inf} 的原本目的。建议改成 4×inf4×\text{inf}。
PYTHON
finf=4*inf;
fill(b,-finf);
s=0;
for i in n:
  input(a[i]);
  a[i]+=inf;
for i in 1~n:
  add(a[i],finf,1); # a[i]~inf 加一
for i in n:
  b[query(0,a[i])]=a[i];
for i in 1:
  if(b[i]=-finf) b[i]=s;
  else s=b[i];
for i in n:
  a[i]=b[i]-inf;

说点别的

  1. inf\text{inf} 最小可以为 max⁡(a)\max(a)。
  2. 没 sort 快活着干啥
  3. 其实如果 log⁡inf>n\log \text{inf}>n 可以暴力插入。
其实可能有很多人想到了这个算法。但是可能我因为过于自大将其写了下来，浪费大家的时间，抱歉。
ヾ(•ω•`)o
希望你们能对算法做些优化！

评论

共 22 条评论，欢迎与作者交流。

正在加载评论...