请问我通过数组下标映射实现的排序算法属于什么类型？

你实现的是计数排序（Counting Sort），属于非比较类排序算法的一种，也可看作单元素桶场景下的桶排序特殊实现，核心逻辑是利用数组下标直接定位元素位置，跳过常规排序的数值比较步骤，最优时间复杂度可以达到线性的O(n+k)（n为待排序元素数量，k为待排序数值的取值范围大小）。

你当前的实现默认适配「待排序元素为非负整数、无重复值」的场景，直接将元素值作为数组下标赋值，即可完成自动排序，对应代码如下：

my @arg = (5, 14, 12, 9, 1, 17, 3, 19, 20, 4, 6, 15, 8, 18, 7, 2, 10, 13, 11, 16);
my @out;
map { $out[$_] = $_ } @arg;
print join " ", @out;

你提到的两个注意点也完全符合计数排序的特性：

• 下标出现空洞是计数排序的典型特征，当待排序数值分布稀疏时会产生额外的空间浪费，输出前过滤掉未赋值的空下标位即可完成压缩。
• 原生实现不支持双精度浮点数，因为数组下标只能对应整数，需要兼容浮点数场景时可以调整数值映射逻辑，或者切换为基于比较的排序算法实现。

基准测试结果 #

你提供的性能测试数据如下：

Rate uniqsort   bubble  mapping perlsort
    uniqsort  82274/s       --     -29%     -87%     -90%
    bubble   115925/s      41%       --     -81%     -86%
    mapping  614399/s     647%     430%       --     -25%
    perlsort 814352/s     890%     602%      33%       --

各测试项说明：

• &uniqsort：调用List::MoreUtils库，通过uniq sort @arr实现
• &bubble：基础冒泡排序实现
• &mapping：本次实现的映射式计数排序
• &perlsort：使用Perl内置sort {$a<=>$b} @arr实现的排序

从测试结果可以看出，当前场景下你实现的计数排序性能远高于冒泡排序和普通去重排序，仅略低于Perl内置的高度优化的排序实现，符合计数排序在适配场景下的性能表现。

内容的提问来源于stack exchange，提问作者Arsenii