将二进制树形数组变成一维数组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]];
}

从技术上讲，它对数组进行了排序 但返回的不是一个一维数组，而是一个反向的二进制树形结构。

如果给定的数组是 [ 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 要么返回一个单一元素 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

这里有一个稍有不同的版本，使用destructuring代替临时变量进行交换，并使用spread操作符来建立输出。

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]]

. 这只是一种审美的呼唤。