我正在尝试找到我最近得到的面试问题的答案，但无法解决。我被要求使用O(1(空间和O(n(时间到位的10位整数对1000万个对象(每个对象包含10位整数和唯一的字符串值(进行排序。出于所有密集的目的，字符串值只会使问题更加困难，但是您不会对其进行分类。
我正在考虑使用计数排序，但这只有在我只是对10位整数进行排序时才有用。对对象进行排序会使事情更加复杂，因为我需要跟踪它们独特的字符串值。我看着radix排序，但似乎使用o(n(作为最坏的案例。
我缺少某种类型吗？
有一个原地(msb(radix sort 。
它是这样的：
- 从第一个开始。
-
将所有元素以等于0等于0的
移动
所有那些等于右1等的人。您通过从两侧移动到中间，在右侧的左侧1交换1，在右侧交换1。
- 考虑下一点的左侧和右侧都重复。
这个过程是这样的：
↓ ↓
0... 1...
--------------- ---------------
↓ ↓ ↓ ↓
00... 01... 10... 11...
------- ------- ------- -------
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
000 001 010 011 101 110 110 111
--- --- --- --- --- --- --- ---
...
时间复杂性是O(bits*n)，空间复杂性为O(bits)。
因此，在恒定数量的位数中，时间复杂度为 O(n)，空间复杂性为 O(1)。
也可以使用计数排序(以同一时间和空间的复杂性(进行此操作。
- 计算每个元素中有多少个。
- 使用此内容，您可以在数组中确定这些元素应该出现的位置。
创建一个查找表(映射索引到偏移，可以是一个数组(，其中包含上述所有起点，将用于确定下一个元素应在哪里。
现在，您循环循环到数组，然后将每个不合适的元素交换到它可以转到的第一个位置，然后对我们所交换的每个元素进行相同的操作，直到当前元素属于其所属的位置为止。<<<<<<<。/p>
使用每个步骤增加查找表中相关元素的偏移。
请注意，不可能两次交换相同的元素，因此这将是线性时间。
听起来都很混乱，所以这是一个例子：
4 5 3 1 2 3 4 4 1 5 4 3 2 3
// counts:
1: 2, 2: 2, 3: 4, 4: 4, 5: 2
// the starting points (offsets) based on the counts:
1 at position 0
2 at position (offset of 1)+(count of 1) = 0+2 = 2
3 at position (offset of 2)+(count of 2) = 2+2 = 4
4 at position (offset of 3)+(count of 3) = 4+4 = 8
5 at position (offset of 4)+(count of 4) = 8+4 = 12
// sorting:
4 5 3 1 2 3 4 4 1 5 4 3 2 3 // out of place, swap with offsets[4] = 8 (offsets[4]++)
^
1 5 3 1 2 3 4 4 4 5 4 3 2 3 // in correct position, moving on (offsets[1]++)
^
1 5 3 1 2 3 4 4 4 5 4 3 2 3 // swap with offsets[5] = 12 (offsets[5]++)
^
1 2 3 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 2 (offsets[2]++)
^
1 3 2 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[3] = 4 (offsets[3]++)
^
1 2 2 1 3 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 3 (offsets[2]++)
^
1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on (offsets[1]++)
^
1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on (offsets[2]++)
^
你明白了...
请注意，计数表和查找表的大小为O(max value)，如果每个数字包含固定数量的位。
O(1)。，您为每个元素进行恒定的工作，所以这是O(n)时间。
一个人可以使用标准的QuickSort枢轴代码将所有带有整数0的项目移至数组的开始。继续在其余元素上继续1、2、3，等等，一旦您在1023上进行了旋转。
。这是通过阵列1024次的迭代，每个枢轴花费O(n(时间，所以O(n(也是。
一种非常相似的方法在实践中更有效的方法只是使用标准的三向速度算法。通常，人们会认为这需要O(n log n(时间，并在最坏的情况下使用O(log n(空间。但是，在这里，整数的域限制为1024个值，因此可以保证在O(n(时间内完成并使用O(1(空间，因为在每个递归呼叫QuickSort中，将永远不会使用枢轴值两次。
[这个答案是一个假设 - 问题中的" 1000万"是n，而" 10位"仍然是固定的]。