0

I'm stuck on this problem(2 weeks). Any idea of how to approach it?.

Let L be a list of n different integer numbers, assume that the elements of x of L are in the range [1,750]. Design a linear ordering algorithm to order the elements of L

I already tried with insertion sort. But i'm not sure if my approach is right:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

Complexity => O(2n) = O(n)

4

4 回答 4

6

尝试基数排序 - http://en.wikipedia.org/wiki/Radix_sort

如果您将给定的 750 视为常数，则它的排序为 O(n)。

基于比较的排序不能以小于 O(nlogn) 的方式排序，但如果值的数量以 D 为界，则可以以 O(D*n) 或 O(n) 进行排序，如果您将 D 视为常数。

于 2013-10-23T05:47:09.133 回答
4

我不会给出完整的方法，但这里有一个应该有帮助的观察。

您已经知道这些数字严格在范围内[1, 750]。在线性时间内找出每个数字中有多少并不是特别困难。

一旦你有了这些信息，你怎么能取回排序的列表（再次，在线性时间）？

至于您给出的方法，这不是插入排序，它更像是桶排序或计数排序（这是我试图暗示的）。我看到的一件事是，如果数组可以包含重复项，您的方法将不起作用。如果你被告知没有，那么你很高兴。否则，您将需要修改您必须处理的内容。

于 2013-10-23T05:49:27.577 回答
2

您可以使用计数排序。对输入进行哈希处理，并在每次插入时增加相应索引处的值。这在 O(n) 时间内排序，额外内存 O(n)。

于 2013-10-23T05:49:53.793 回答
1

这是一些代码：

IntegerSort (Array A):
   Dimension Work as Array[1..750]

   Fill Work with (0)

   For i:=0 to A.Length - 1 
     Work[A[i]]++

   n = 0;
   For i:=1 to 750
      For j :=1 to Work[i] 
         A[n++] = i

由于所有循环都是 O(n)，因此算法也是 O(n)。

Work在一个跨越整个数字范围并以 0 初始化的数组中，将每个元素 Work[k] 加一，对于 A 的所有元素，k=A[i]。

现在通过扫描阵列来重建Work阵列。任何 >0 的元素都表示原始数组中的一个或多个元素。当我们从 1 扫描到 750 时，我们将重建已排序的数组。

于 2013-10-23T06:16:13.860 回答