排序BST使用常量内存为O（n）

本文介绍了排序BST使用常量内存为O（n）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是不是一门功课。只是一个有趣的任务：）

This is not a homework. Just an interesting task :)

鉴于阵列psensted一个完整的二进制搜索3重$ P $。排序使用常量内存在O（n）的阵列。

Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory.

例如：

树：

8 / \ 4 12 /\ / \ 2 6 10 14 /\ /\ /\ /\ 1 3 5 7 9 11 13 15

阵列：8,4，12，2，6，10，14，1，3，5，7，9，11，13，15

Array: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

输出：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15

Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

推荐答案

这是可能的，人们称之为功课大概还没有尝试解决它。​​

It is possible, people calling it homework probably haven't tried solving it yet.

我们使用以下作为子例程：

We use the following as a sub-routine:

Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to b1 a1 b2 a2 ... bn an

有一个解决方案可以在这里找到： arxiv/abs/0805.1598

A solution for that can be found here: arxiv/abs/0805.1598

我们使用如下：

执行上面交错的第2 ^（K + 1） - 2个元素，开始在k = 1的重复对于k = 2，3​​等，直到你走过去的数组的末尾

Do the above interleaving for the first 2^(k+1) - 2 elements, starting at k=1 repeating for k=2, 3 etc, till you go past the end of array.

例如您的阵列中，我们得到（交错确定括号套）

For example in your array we get (interleaving sets identified by brackets)

8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 [ ][ ] 4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 1, interleave 2) [ ][ ] 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 2, interleave 6) [ ][ ] 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (k = 3, interleave 14)

所以，总时间为N + N / 2 + N / 4 + ...... = O（N）。 使用空间是O（1）。

So the total time is n + n/2 + n/4 + ... = O(n). Space used is O(1).

这本著作可以通过归纳证明。

That this works can be proved by induction.