排序算法问题
排序算法问题
提问于 2010-10-11 11:13:38
这里有一个脑筋急转弯，已经在我的脑海中停留了几天。
我们有一个包含n个元素的序列S。每个元素都是0，n^2-1范围内的整数。描述一种在O(n)时间内对S进行排序的简单方法。
我可能遗漏了一些显而易见的东西，但如果有任何见解，我会很感激。
回答 4
Stack Overflow用户
回答已采纳
发布于 2010-10-11 11:17:45
Bucket Sort!
存储桶排序是一种通过将数组划分为多个存储桶来实现的排序算法。然后，使用不同的排序算法或通过递归地应用桶排序算法，对每个桶进行单独排序。它是一种分布排序，在最高到最低有效数字中是基数排序的近亲。桶排序是归类排序的一种推广。由于桶排序不是比较排序，因此Ω( not )下限不适用。计算复杂度估计包括存储桶的数量。
Stack Overflow用户
发布于 2010-10-11 11:19:10
写入基数n并进行桶排序，对每个桶进行计数排序(桶对应于基数n中的数字)。
O(n)时间，O(n)空间。
Stack Overflow用户
发布于 2010-10-11 11:22:42
Radix Sort! (这只是存储桶排序的一个特例。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3903310
复制相关文章
相似问题
腾讯云开发者
