algorithm - 在线性时间内对 0 到 n^2 – 1 范围内的 n 个数字进行排序

Question

如何使用两次计数排序对数组的元素进行排序？

是否会使用两次精确计数排序？

我知道它与基数排序（这是计数排序的子程序）有关，其中元素通过一次考虑每个数字进行排序。

有关更多详细信息：- https://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/

（请不要将其声明为重复我已经检查过与此相关的帖子。）

将数字转换为基数 n 后，元素将如何变为两位数？请告诉我这个好吗？

提前致谢。

Answer 1

文章中描述的技巧是将数组的元素视为以 n 为底的 2 位数字，并使用两次计数排序对它们进行排序。

这个想法是按底部数字对数字进行排序（使用稳定的排序算法），然后按较高的数字对数字进行排序（使用相同的稳定排序算法）导致数字被排序。这两个步骤可以被认为是基数排序的一种形式，除了它不是按位排序，而是按以 n 为底的数字排序。

鉴于数字都在 0..n-1 范围内，可以使用计数排序在线性时间内完成两个排序步骤中的每一个。为了使计数排序稳定，需要处理一些繁琐的细节，但文章中提供了这些细节（和代码）。