恒为on方时间复杂度的排序算法

在计算机科学中，时间复杂度为 $O(n)$ 的排序算法被称为线性时间排序算法。目前有两种常用的线性时间排序算法，分别是计数排序（Counting Sort）和基数排序（Radix Sort）。

1. 计数排序

计数排序是一种非比较排序算法，其基本思想是对于给定的输入序列中的每一个元素 $x$，确定该序列中值小于 $x$ 的元素的个数，然后可以将 $x$ 直接放到第 $n+1$ 个位置上。具体步骤如下：

1. 找出待排序的数组中最大和最小的元素。

2. 统计数组中每个值为 $i$ 的元素出现的次数，存入数组 $C$ 的第 $i$ 项。

3. 对所有的计数累加（从 $C$ 中的第一个元素开始，每一项和前一项相加）。

4. 反向填充目标数组：将每个元素 $i$ 放在新数组的第 $C_i$ 项，每放一个元素就将 $C_i$ 减去 $1$。

计数排序的时间复杂度为 $O(n+k)$，其中 $n$ 是待排序序列的长度，$k$ 是待排序序列中的最大值和最小值的差。当待排序序列的最大值和最小值相差不大时，计数排序的效率比较高。

2. 基数排序

基数排序是一种多关键字比较排序算法，其基本思想是按照低位先排序，然后收集；再按照高位排序，然后再收集；依此类推，直到最高位。这样通过对每个关键字的排序，达到了整体排序的目的。具体步骤如下：

1. 取得数组中的最大数，并取得位数。

2. arr 为原始数组，从最低位开始取每个位组成 radix 数组。

3. 对 radix 进行计数排序（利用计数排序中的“每个桶里放置当前桶和前面桶的元素个数和”），从而得到排序结果。

基数排序的时间复杂度为 $O(d(n+k))$，其中 $d$ 是数字位数，$n$ 是待排序序列的长度，$k$ 是基数，通常是 $10$。当数字位数 $d$ 较小时，基数排序的效率比较高。