1.排序

  • 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function example(arr) {
      for(let i = 0; i < arr.length - 1; i++) {
        for( let j = 0; j < arr.length - 1 - i; j++){
          if(arr[j] > arr[j + 1]){
            let temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }
      return arr;
    }

    let arr = [3, 44, 13, 1, -1]
    console.log(example(arr)) // [-1,1,3,13,44]

  • 直接插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    let arr = [3, 44, 13, 1, -1]
    // 稳定性: 稳定 时间复杂度: o(n^2)
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        j = i - 1;
        while (j >= 0 && temp < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    console.log(arr) // [-1,1,3,13,44]


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

  • 选择排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    let arr = [3, 44, 13, 1, -1];
    for (let i = 0; i < arr.length - 1; i++) {//遍历数组
        let min = arr[i];//防止arr[i]发生变化
        for (let j = i + 1; j < arr.length; j++) {//双重遍历，查找最小的数进行交换，跟冒泡不一样的地方在于，选择排序，假如第4位更小，则是1，4位交换，不是3，4位交换
            if (min > arr[j]) {
                let temp = min;
                min = arr[j];
                arr[j] = temp;
            }
        }
        arr[i] = min;
    }
    console.log(arr) // [-1,1,3,13,44]


    方法二
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                var sum = 0;
                sum = arr[i];
                arr[i] = arr[j];
                arr[j] = sum;
            }
        }
    }
    console.log(arr) // [-1,1,3,13,44]

  • 快速排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    let arr = [3, 44, 13, 1, -1];
    function arrSort(arr) {
        if (arr.length <= 1) {
            return arr
        };
        var pivotIndex = Math.floor(arr.length / 2);
        var pivot = arr.splice(pivotIndex, 1)[0];//取出中间的数字，比如第一次就取出13
        var left = [];
        var right = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < pivot) {//第一次运算，如果小于13就进入左数组，大于就进入右数组
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return arrSort(left).concat([pivot], arrSort(right));//递归，再把左数组分成两半进行排序，右数组同理。
    }
    console.log(arrSort(arr))

  • 希尔排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    let arr = [3, 44, 13, 1, -1];
    function arrSort(arr) {
        let gap = Math.floor(arr.length / 2);
        while (gap >= 1) {
            for (let i = gap; i < arr.length; i++) {
                let j, temp = arr[i];
                for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
            gap = Math.floor(gap / 2);
        }
        return arr;
    }
    console.log(arrSort(arr))