将二叉树数组转为一维数组JavaScript

Question

我正在尝试对冒泡排序进行递归编程。到目前为止，这是我的代码：

function recursive_bubble_sort(array) {
    if (array.length === 1) {
        return array;
    }

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            var temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }

    return [recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]];
}

从技术上讲，它对数组进行排序，但 return 不是一维数组，而是反向二叉树结构。

如果给定的数组是 [ 8, 2, 5, 1 ]，
输出将是 [ [ [ [ 1 ], 2 ], 5 ], 8 ]。
我怎样才能更改代码以使输出如下所示：[ 1, 2, 5, 8 ]?

Answer 1

问题出在return语句

return [recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]];

但是，由于 recursive_bubble_sort 要么 returns 单个元素 recursive_bubble_sort 要么数组（另一个 return），您需要同时处理两者。

一种简单的方法是只使用 Array#concat - 如果给它一个元素，它会将它添加到数组中，如果给它一个数组，它会添加所有元素。这确保结果始终是平坦的：

你也可以

function recursive_bubble_sort(array) {
    if (array.length === 1) {
        return array[0];
    }

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            var temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }

    return [].concat(recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]);
}

console.log(recursive_bubble_sort([ 8, 2, 5, 1 ]))

Answer 2

这是一个略有不同的版本，使用解构而不是临时变量进行交换和展开运算符来构建输出：

const recursive_bubble_sort = (arr) => {
  if (arr.length < 2) {return arr}

  for (let i = 0; i < arr.length - 1; i ++) {
    if (arr[i] > arr[i + 1]) {
      [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
    }
  }

  return [... recursive_bubble_sort (arr.slice(0, -1)), ... arr.slice(-1)]
}

console .log (recursive_bubble_sort ([8, 2, 5, 1]))

最后一行也可以是

  return [... recursive_bubble_sort (arr.slice(0, -1)), arr[arr.length - 1]]

。简直就是审美呼唤。

将二叉树数组转为一维数组JavaScript

Turn a binary tree array into a one-dimensional array JavaScript

javascript

arrays

sorting

recursion

bubble-sort