javascript - 如何以非随机但数学的顺序从数组中进行选择

Question

我可以在没有公式的情况下完成此任务，但我正在努力创建一个数组选择方法，该方法可以几乎随机地进行选择。原因是我需要在数组以 2 的幂增长时进行选择。数组索引的内容并不重要。

[0] // select index 0
[0,1] // select index 1 then 0
[0,1,2,3] // 3, 1, 2, 0
[0,1,2,3,4,5,6,7] // 7, 3, 5, 1, 6, 2, 4, 0
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] // 15,7,11,3,13,5,9,1,14,6,12,4,10,2,8

我最终想出了这种模式，因为它不会随着数组扩展至 2 的幂而降级。选择保持不变。这与对数组进行排序无关，而只是按特定顺序选择预​​先排序的数组。我已经广泛寻找可能的解决方案，但自从我进行认真的数学计算以来已经有一段时间了，我确信这是需要的。

我看到的模式并不明显，但我会尝试更多地解释它。它与二叉树有关。在根目录下，您有 [0]。

                     [0]
                    [0,1]
                  [0,1,2,3]
               [0,1,2,3,4,5,6,7]
   // for example
                ___ 20 ___
               /          \
              10          30
            /    \       /    \
           5      15    25    35
          / \    / \    / \   / \
         1   7  12 18  23 27 31  37

我需要创建一个第三个数组，该数组具有正确的插入顺序，而不会导致重新平衡。

[20,30,10,35,15,25,5,37,18,27,7,31,12,23,1]

此选择模型继续随 Btree 一起增长，这将导致树无法通过将这些值插入到自平衡树中来重新平衡。

Answer 1

下面的函数会将一个已排序的数组按顺序插入另一个数组，如果另一个数组实际上是 AVL 树，则不会导致重新平衡。它不是最有效的，但它展示了如何完成它的示例。

var sorted = [1, 5, 7, 10, 12, 15, 18, 20, 23, 25, 27, 30, 31, 35, 37];
console.log("sorted: ", sorted)

function insertBalanced(sortedArray, avlTree) {
  var size = sortedArray.length;
  var result = avlTree;
  var indexesUsed = [];
  function halfIndexes(depth) {
var slices = Math.pow(2, depth);
for(var i = 1; i < slices;i++) {
  var nextIndex = Math.floor(size * i / slices);
  if (!indexesUsed.includes(nextIndex)) {
    indexesUsed.push(nextIndex);
    result.push(sortedArray[nextIndex]);
  }
}
if (indexesUsed.length < size) {
  halfIndexes(depth + 1);
}
  };
  return halfIndexes(1);
}
var someEmptyAvlTree = [];
insertBalanced(sorted, someEmptyAvlTree);
console.log("avlTree", someEmptyAvlTree);