O(n) 最坏情况下的基数排序算法
Radix sort algorithm with O(n) worst case
假设给定了一个整数数组 A，大小为 n。你提前知道A的O(√n)个元素可以大于2020(n)^(5) − 5n，A的剩余元素在[1, 2020n^5 − 5n]范围内。事实证明，在这种情况下，最坏情况下A可以在O(n)时间内排序。
我正在尝试解决这个有趣的算法问题，我的直觉是使用基数排序作为解决方案的一部分。难倒我的部分是 O(√n) 运行时，所以任何找到这种算法的指示都将不胜感激！
将范围内的元素与范围外的元素分开（O（n））。对范围内的元素进行基数排序（以 n 为基数；对于 n ≥ 2020，这需要六遍，并且是 O(n)）。对超出范围的元素进行插入排序（有 √n 个，因此 O(√n²) = O(n)）。合并两个排序数组 (O(n)).
假设给定了一个整数数组 A，大小为 n。你提前知道A的O(√n)个元素可以大于2020(n)^(5) − 5n，A的剩余元素在[1, 2020n^5 − 5n]范围内。事实证明，在这种情况下，最坏情况下A可以在O(n)时间内排序。
我正在尝试解决这个有趣的算法问题，我的直觉是使用基数排序作为解决方案的一部分。难倒我的部分是 O(√n) 运行时，所以任何找到这种算法的指示都将不胜感激！
将范围内的元素与范围外的元素分开（O（n））。对范围内的元素进行基数排序（以 n 为基数；对于 n ≥ 2020，这需要六遍，并且是 O(n)）。对超出范围的元素进行插入排序（有 √n 个，因此 O(√n²) = O(n)）。合并两个排序数组 (O(n)).