JavaScript 相关算法

冒泡排序

冒泡排序的思路：遍历数组，然后将最大数沉到最底部；
时间复杂度：O(N^2)；
空间复杂度：O(1)

作为最简单的排序算法之一，冒泡排序的思想是，从左到右依次比较两个存储数据的大小，如果第一个数大于第二个数，就交换两个数据，这样一轮比较之后，最大的数会放在后面，这样，每次循环比较，本轮中的最大值都会排到最后，直到循环结束，实现数组升序。
动图演示如下：

代码如下

/*
 *  冒泡排序
 *  1、比较相邻的两个元素，如果前一个比后一个大，则交换位置。
 *  2、比较完第一轮的时候，最后一个元素是最大的元素。
 *  3、这时候最后一个元素是最大的，所以最后一个元素就不需要参与比较大小。
 */

function BubbleSort(arr) {
    if (arr === null || arr.length === 0) {
        return [];
    }
    let len = arr.length;
    // 比较轮数
    for (let i = 0; i < len - 1; i++) {
        // 每轮比较次数，次数=长度-1-此时的轮数
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
console.log('冒泡排序：', BubbleSort([10, 9, 7, 200, 100]));   // [7, 9, 10, 100, 200]

选择排序

选择排序的实现思路：遍历数组，把最小数放在头部；
时间复杂度：O(N^2)；
空间复杂度：O(1)

选择排序，遍历数组，把最小数放在头部。首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕。
动图演示如下：

代码如下

/*
 *  选择排序
 *  原理：遍历数组，把最小数放在头部
 *  1、首先从原始数组中找到最小的元素，并把该元素放在数组的最前面
 *  2、然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕
 */
function SelectionSort(arr) {
    if (arr === null || arr.length === 0) {
        return [];
    }
    let len = arr.length, minIndex;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
console.log('选择排序：', SelectionSort([10, 9, 7, 200, 100]));      // [7, 9, 10, 100, 200]