给定一个大小为 100 的未排序值数组（列表有 100 个元素），每个值都是从 [0…1000] 范围内随机抽取的。设计一种算法以在线性时间内对给定列表进行排序（即 O(N) 最坏情况性能）。
提示：利用预先知道值范围的事实（即从 1 到 1000）
这是我班的硬件问题之一。他想要执行上述操作的函数的伪代码。我只是想不出一个具有 O(N) 最坏情况性能的函数。
PS - 它不应该像基数排序那样复杂。PSS - 我只是想知道如何做到这一点。不找人做我的功课。
这是在Java顺便说一句。
谢谢！
问问题
2802 次
6 回答
6
看看位图排序。它通过使用一组未排序的值作为数组中的索引来工作，并在 O(N) 时间内运行。
于 2013-03-22T00:50:53.770 回答
4
我相信您正在寻找的是Counting Sort。您跟踪每个数字出现的次数，然后按顺序将它们打印回来。
于 2013-03-22T01:03:20.190 回答
0
Nick is correct (give him credit--I'm only answering because it wouldn't fit into the comment field).
You would define an array with 1,001 elements all initialized to zero. You read the 100 values one at a time, incrementing the array element which has the same index as the value that you are reading. After you do this 100 times, you will have an array of 1,001 elements (mostly still zero), and you simply print the number 0 as many times as specified by the value in the 0th array element, then the number 1 as many times as specified by the value in the 1st array element, etc. This sounds slow, but since it is an O(n) algorithm, it is faster than any other sorting method, but works only since you know the inputs are all integers within the range of 0 to 1,000 (1,001 total possibilities).
于 2013-03-22T01:15:48.190 回答
0
Yeah, the "counting sort" would be O(n) + O(N) (where n = 100 & N = 1000). But like all schemes that claim to be better than n log(n) it "cheats", because the O(N) component is in reality an N log N component when you take into account the cost of expanding memory -- memory performance is log N to memory size. It's just that, for the particular processor in question, memory size is fixed and hence the log N factor is buried.
于 2013-03-22T01:17:34.967 回答
0
在这种情况下计数排序的成本似乎是 O(N+Nsqrt(N))=O(N^3/2)。我认为这可以使用@Daniel_Williams 告诉我们的 radix_sort 来改进。例如参见麻省理工学院公开课程第 5 讲https://www.youtube.com/watch?v=0VqawRl3Xzs
于 2013-03-22T02:24:57.917 回答
0
这通常是他们在您的第一堂算法课中为此教授的算法：http ://en.wikipedia.org/wiki/Radix_sort
于 2013-03-22T01:31:37.130 回答