js基础扫盲 - 常用的排序(冒泡排序,选择排序,插入排序)

冒泡排序

从前向后,相邻两个元素进行比较,依次移动。

function bubbleSort (list) {
    if (!list instanceof Array) {
        return []
    }
    for (let i = 0; i < list.length; i++) {
        for (let j = 0; j < list.length - i; j++) {
            if (list[j] > list[j+1]){
                [list[j] , list[j+1]] = [list[j+1], list[j]]
            }
        }
    }
    console.log(list);
    return list
}
bubbleSort([3,2,6,9,45,4,8,1])

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

选择排序

从前向后,对比最小值替换到最前面

function selectSort (list) {
    if (!list instanceof Array) {
        return []
    }
    for (let i = 0; i < list.length ; i++) {
        for (let j = i+1; j < list.length; j++) {
            if (list[i] > list[j]) {
                let temp = list[j]
                list[j] = list[i]
                list[i] = temp
            }
        }
    }
    return list
}
selectSort([3,2,6,9,45,4,8,1])

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

插入排序

将前面的数据定义为有序数组,将当前选中的 在 有序数组中遍历,插入到适当的位置

    function insertSort(arr){
        for (var i = 0; i < arr.length; i++) {
            var current = arr[i]
            for (var j = i - 1; j >=0 && arr[j] > current; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = current;
        }
        return arr
    }
    console.log(insertSort([3,2,6,9,45,4,8,1]));

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

随机浏览