在 O(n) 时间和 O(1) 额外内存中对 1000 万个对象进行排序
Sorting 10 million objects in O(n) time and O(1) extra memory
我正在尝试为我最近遇到但无法解决的面试问题找到答案。我被要求使用 O(1) space 和 O(n) 时间按 10 位整数对 1000 万个对象（每个对象包含一个 10 位整数和一个唯一的字符串值）进行排序。对于所有密集的目的，字符串值只会使问题变得更加困难，但您不会根据它对对象进行排序。
我正在考虑使用计数排序，但是，这只有在我只是对 10 位整数进行排序时才有效。对对象进行排序会使事情变得有点复杂，因为我需要跟踪它们的唯一字符串值。我查看了基数排序，但它似乎使用 O(n) 作为最坏情况。
我是否遗漏了某种类型？
可以使用标准的快速排序主元代码将整数为 0 的所有项移动到数组的开头。继续对其余元素进行 1、2、3 等操作，在以 1023 为中心后停止。
这遍历数组1024次，每个主元花费O(n)时间，O(n)也是如此。
一种非常相似但在实践中更有效的方法就是使用标准的三向快速排序算法。人们通常会认为这需要 O(n log n) 时间，并且在最坏的情况下使用 O(log n) space。但是在这里，整数的域被限制为 1024 个值，因此保证在 O(n) 时间内完成并使用 O(1) space，因为在对快速排序的每次递归调用中，主值永远不会使用两次。
[本答案假设题中“1000万”为n，“10位”不变]
There's an in-place (MSB) radix sort.
事情是这样的：
- 从第一位开始。
将该位等于0的所有元素向左移动
以及右边那个位等于 1 的所有那些。
您通过从两侧移动到中间，将左侧的 1 与右侧的 0 交换，类似于快速排序。
- 考虑到下一位，在左侧和右侧递归。
过程是这样的：
↓ ↓
0... 1...
--------------- ---------------
↓ ↓ ↓ ↓
00... 01... 10... 11...
------- ------- ------- -------
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
000 001 010 011 101 110 110 111
--- --- --- --- --- --- --- ---
...
时间复杂度O(bits*n)，space复杂度O(bits)。
所以在位数不变的情况下，时间复杂度为O(n)，space复杂度为O(1)。
也可以使用 计数排序 来做到这一点（具有相同的时间和 space 复杂度）。
- 计算每个元素有多少。
- 使用它您可以确定这些元素应该出现在数组中的什么位置。
创建一个查找table（将索引映射到偏移量，可以是一个数组）包含所有上述起点，这将用于确定下一个元素应该去哪里。
现在你遍历数组并将每个不合适的元素交换到它可以到达的第一个位置，然后对我们交换的每个元素执行相同的操作，直到当前元素所在的位置它属于。
每一步增加查找中相关元素的偏移量table。
请注意，不可能将同一个元素交换两次，因此这将是线性时间。
这一切听起来很混乱，所以这里有一个例子：
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]++)
^
你明白了...
请注意，计数 table 和查找 table 的大小为 O(max value)，如果每个数字包含固定位数，则为 O(1)。
并且您为每个元素做的工作量是恒定的，所以这是 O(n) 时间。
我正在尝试为我最近遇到但无法解决的面试问题找到答案。我被要求使用 O(1) space 和 O(n) 时间按 10 位整数对 1000 万个对象（每个对象包含一个 10 位整数和一个唯一的字符串值）进行排序。对于所有密集的目的，字符串值只会使问题变得更加困难，但您不会根据它对对象进行排序。
我正在考虑使用计数排序，但是，这只有在我只是对 10 位整数进行排序时才有效。对对象进行排序会使事情变得有点复杂，因为我需要跟踪它们的唯一字符串值。我查看了基数排序，但它似乎使用 O(n) 作为最坏情况。
我是否遗漏了某种类型？
可以使用标准的快速排序主元代码将整数为 0 的所有项移动到数组的开头。继续对其余元素进行 1、2、3 等操作，在以 1023 为中心后停止。
这遍历数组1024次，每个主元花费O(n)时间，O(n)也是如此。
一种非常相似但在实践中更有效的方法就是使用标准的三向快速排序算法。人们通常会认为这需要 O(n log n) 时间，并且在最坏的情况下使用 O(log n) space。但是在这里，整数的域被限制为 1024 个值，因此保证在 O(n) 时间内完成并使用 O(1) space，因为在对快速排序的每次递归调用中，主值永远不会使用两次。
[本答案假设题中“1000万”为n，“10位”不变]
There's an in-place (MSB) radix sort.
事情是这样的：
- 从第一位开始。
将该位等于0的所有元素向左移动
以及右边那个位等于 1 的所有那些。您通过从两侧移动到中间，将左侧的 1 与右侧的 0 交换，类似于快速排序。
- 考虑到下一位，在左侧和右侧递归。
过程是这样的：
↓ ↓
0... 1...
--------------- ---------------
↓ ↓ ↓ ↓
00... 01... 10... 11...
------- ------- ------- -------
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
000 001 010 011 101 110 110 111
--- --- --- --- --- --- --- ---
...
时间复杂度O(bits*n)，space复杂度O(bits)。
所以在位数不变的情况下，时间复杂度为O(n)，space复杂度为O(1)。
也可以使用 计数排序 来做到这一点（具有相同的时间和 space 复杂度）。
- 计算每个元素有多少。
- 使用它您可以确定这些元素应该出现在数组中的什么位置。
创建一个查找table（将索引映射到偏移量，可以是一个数组）包含所有上述起点，这将用于确定下一个元素应该去哪里。
现在你遍历数组并将每个不合适的元素交换到它可以到达的第一个位置，然后对我们交换的每个元素执行相同的操作，直到当前元素所在的位置它属于。
每一步增加查找中相关元素的偏移量table。
请注意，不可能将同一个元素交换两次，因此这将是线性时间。
这一切听起来很混乱，所以这里有一个例子：
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]++)
^
你明白了...
请注意，计数 table 和查找 table 的大小为 O(max value)，如果每个数字包含固定位数，则为 O(1)。
并且您为每个元素做的工作量是恒定的，所以这是 O(n) 时间。