JS: 冒泡排序和二叉树列

冒泡排序

冒泡排序是一种常见的排序算法，它重复地比较相邻两个元素，并且如果它们的顺序错误就交换它们。这个过程一直持续到整个数组排序完成为止。

冒泡排序的算法步骤：

1. 比较相邻的元素。如果第一个元素比第二个元素大，就交换它们的位置。
2. 对每一对相邻元素重复以上步骤，直到到达数组的末尾。这样一趟过后，最大的元素就会被移动到数组末尾。
3. 针对所有的元素重复以上步骤，除了已经被排序的元素，每一趟都会将剩余元素中最大的数归位。
4. 重复步骤2-3，直到整个数组排序完成。

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

冒泡排序算法的时间复杂度是 O(n^2)，不适合大型数组的排序，但对于小型数组或者基本有序的数组，它的性能还是不错的。

二叉树排序

二叉树排序是一种基于二叉树数据结构的排序算法。它的基本思想是将待排序的数据依次插入到一个二叉查找树中，然后按照中序遍历的顺序输出即可得到排序结果。

二叉树排序的算法步骤：

1. 创建一个空的二叉查找树（BST）。
2. 遍历待排序的数组，将每个元素依次插入到二叉查找树中。
3. 对二叉查找树进行中序遍历，即可得到有序的结果。

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    let newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  inOrderTraversal(callback) {
    this.inOrderTraversalNode(this.root, callback);
  }

  inOrderTraversalNode(node, callback) {
    if (node !== null) {
      this.inOrderTraversalNode(node.left, callback);
      callback(node.value);
      this.inOrderTraversalNode(node.right, callback);
    }
  }
}

var arr = [64, 34, 25, 12, 22, 11, 90];
var bst = new BinarySearchTree();

for (var i = 0; i < arr.length; i++) {
  bst.insert(arr[i]);
}

var sortedArr = [];
bst.inOrderTraversal((value) => {
  sortedArr.push(value);
});

console.log(sortedArr); // [11, 12, 22, 25, 34, 64, 90]

二叉树排序算法的时间复杂度取决于树的结构，平均情况下为 O(nlogn)，最坏情况下为 O(n^2)。

总结

冒泡排序和二叉树排序都是常见的排序算法，它们都可以用于对数组进行排序。冒泡排序算法简单易懂，适用于小型数组或者基本有序的数组；而二叉树排序算法则通过将元素插入到二叉查找树中，然后进行中序遍历来实现排序，适用于处理大型数组。选择合适的排序算法取决于问题规模和数据特点。

本文来自极简博客，作者：烟雨江南，转载请注明原文链接：JS: 冒泡排序和二叉树列