用于交错字符和数字数组的算法
有一个类似的阵列[a,b,2,c,3,d,4,1].必须将其修改为[a,2,b,3,c,4,d,1]就地数组.
也就是说,从散布有字母和数字的原始数组中,修改后的版本应包含相同的元素,使得数组具有交替的字母和数字,同时保留其原始的相对顺序.
它可以通过使用两个指针轻松完成,并将修改后的版本输出到一个新数组中,但必须在O(N)时间和O(1)空间上就地完成.是否有可能,如果是的话,怎么样？
O(N) 就地算法是可能的。您可以首先将所有字母排序到数组的开头，将所有数字排序到数组的末尾。然后就地转置2x( N /2) 矩阵，将数组前半部分的所有元素放置到偶数位置，将其他元素放置到奇数位置。这个问题解释了如何进行这种换位（实际上，那里描述的算法应该反向应用）。
最棘手的部分是排序。它应该既稳定又到位。
在 O( N 2 ) 时间内排序是微不足道的。插入排序或冒泡排序就可以了。
O( N log N ) 时间更复杂。使用稳定的就地合并排序，如本答案所述。这个答案提供了一对链接，描述了可用于组成 O( N ) 算法的想法，该算法比稳定的就地合并排序更简单，但仍然相当复杂，所以我只给出了它的一个草图。
将阵列分为两个区域。其中之一将用于临时存储算法其他部分所需的一些数据（由于该区域仍应存储数组元素，因此任何附加信息均按这些元素的顺序进行编码）。其他区域被解释为方阵，其中元素应排序，先行，然后列。对两个区域进行排序后，对每个区域应用转置算法，以将字符和数字放在正确的位置。
1. 使用数组的一部分进行临时存储
数组的大多数元素被组织为大小为K的方阵。K是最大偶数，使得 2 * 8 * K + K 2不大于N。临时存储的大小M = N - K 2，约等于2*8*sqrt( N )。
要准备M 个元素用于临时存储，请扫描数组的前M 个元素并确定在此范围内最少表示的元素类型。例如，让它为“数字”。将数字打包成一组大小为M /2 的数字。为此，请迭代交换字母和数字块，如下例所示：
ddaaaddddadddaaaaad
aaaDDddddadddaaaaad
aaaaDDDDDDdddaaaaad
aaaaaaaaaDDDDDDDDDd
当单组中收集到至少M /2 个数字时停止。块交换过程（也可以称为就地子阵列旋转）可以作为本答案的第一个算法来实现，也可以如下实现：
- 反转数字块
- 反转数字块
- 将两个块一起反转
例子：
123abcd
321abcd
321dcba
abcd123
将数字打包成大小为M /2的组需要移动最多 ( M /2) 2 个数字和最多N /2 个字母，因此这可以在 O( N ) 时间内完成。
确切地说，它是 O( N log 2 U ) 时间，对于 ASCII 字符进行排序是可以的，但是如果我们需要对其他类型的值进行排序（U是值集的大小），那么这个时间就太大了。为了将运行时间提高到 O( N * log U * log log U )，请从大小为 2 * K的较小临时存储开始，使用它对 log U范围进行排序，然后通过log 中的块交换过程成对合并这些范围记录U步骤以获得适当大小的临时存储。
此时，我们有M /2 大小的数字块，前面是字母块（可能更大）。使用块交换过程使两个块大小相等M /2。
为了在临时存储器中存储数据位，我们可以交换位置 i 和 i + M /2处的元素。如果位置 i 存储字母并且位置 i + M /2 存储数字，则我们有零位。如果数字在前，则我们有非零位。8 个连续位编码单个字符。这意味着，我们可以在临时存储中记住最多K个字符。
在临时存储器中存储位的其他替代方案是其“数字”一半。每个数字可以存储为“0”..“9”（表示位 0），或存储为“a”..“j”（表示位 1）。如果可能的字母数量至少是数字数量的 3 倍，我们可以在每个值中存储 2 位。为了从每个值中挤出 4 位，我们可以将每 2 位数字打包成一个字节；这给出了M /4 空闲字节；所以M可以减少到 4 * K。
2. 对矩阵的行进行排序
从这一点来看，我们应该重新排列数组的主要区域，使用临时存储作为附加内存。确定在大小为 2 * K的子数组中最少表示哪种元素。例如，让它为“数字”。顺序扫描数组，将数字移动到临时存储并将字母打包成连续序列。当收集到K 个数字时，我们有 L 个字母按顺序排列，并且 L >= K。将最后 L% K个字母移至未占用区域的末尾，并用临时存储中的数字填充剩余的未占用区域。然后继续按顺序扫描阵列。
此过程仅复制数组的每个元素一次或两次，因此需要 O( N ) 时间才能完成。最后，所有字母/数字块都对齐，以便矩阵的每一行都包含一种元素。
3. 对矩阵的列进行排序
这是先前过程的简化版本。对于每个矩阵列，将数字移动到临时存储并将字母打包到连续的行中，然后将数字从临时存储复制到未占用的行。
这个过程也需要 O( N ) 时间才能完成。最后，数组的主要区域已完全排序。现在对临时存储进行排序（将零写入其每个“位”）。
4. 转置数组
剩下的唯一步骤是转置数组的临时存储区和主区域，以便字符和数字位于正确的位置。（请注意，不是一个K x K矩阵，而是两个由两个子数组组成的 2 x J 矩阵，并使用链接答案之一中提到的算法进行转置）。
这个过程以及整个算法需要 O( N ) 时间。
第二个算法。
由于 ASCII 仅包含 10 个数字和 52 个字母，我们可以通过以下方式显着简化算法：
- 使用 BASE64 编码打包最后 1/3 的值，这会提供N /12 字节的可用空间（用作临时存储）。
- 使用此空间作为临时存储对前 1/3 的值进行排序：确定在大小为N /6的子数组中最少表示哪种元素；例如，让它为“数字”；顺序扫描数组，将数字移动到临时存储并将字母打包成连续序列；然后将临时存储复制到未占用的空间；对接下来的N /6 个元素重复此操作。
- 解压缩最后 1/3 的值，打包前 1/3 的值。
- 对最后 2/3 的值进行排序（对N /6 元素进行 4 次排序）。
- 解压缩前 1/3 的值。
- 此时我们有 12 组字符（大小可变）。使用块交换程序在这些组之间移动这些组的块，并按正确的顺序（字母、数字等）组成 12 个大小相等的组。
- 转置6 对字符组。实际上，这里可以使用简单的转置算法。对所有未标记的元素（第 7 位为零）应用循环引导算法，并在元素移动时将其第 7 位设置为 1。完成后，清除所有标记。
第三种算法。
解决此问题的其他方法是将所有字母排序到数组的开头，将所有数字排序到末尾，使用（一些修改的）就地稳定基数排序，如本 pdf中所述。排序后，应用前面提到的转置算法。
这里最棘手的事情是基数排序算法的压缩部分。我们无法从每个值中保存一位。相反，我们应该使用算术编码。