算法-冒泡排序、插入排序、选择排序

[cookiepool]

核心

冒泡、插入、选择排序都有一个共同点，将待排序数列分为已排序和未排序两部分。在未排序的部分中查找一个最值，放到已排序数列的恰当位置。

具体到代码层面，外层循环的变量用于分割已排序和未排序数，内层循环的变量用于在未排序数中查找。从思路上看，这三种算法其实是一样的，所以时间复杂度也相同。

冒泡排序

核心：相邻直接进行比较，每次内循环比较一轮过后，都会找到一个最大或最小值。

这里贴出我的错误写法：

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

let arr = [12, 89, 33, 6, 8, 99, 23];
bubbleSort(arr);
console.log(arr);

输出的结果是：

Array(7) [12, 6, 8, 23, 33, 89, 99]

还有一种写法，结果是正确的，但是思想应该不对，我都不知道自己怎么写的

let arrTest = [12, 12, 89, 33, 6, 8, 99, 23];
function bubbleSort(arrTest) {
  for (let i = 0; i < arrTest.length - 1; i++) {
    for (let j = i + 1; j < arrTest.length; j++) {
      if (arrTest[i] > arrTest[j]) {
        let temp = arrTest[i];
        arrTest[i] = arrTest[j];
        arrTest[j] = temp;
      }
    }
  }
}
bubbleSort(arrTest);
console.log(arrTest);

输出结果：

Array(8) [6, 8, 12, 12, 23, 33, 89, 99]

这里我做了个分析，发现确实不符合冒泡规则：

那么一个正确的冒泡排序应该是这样的：

• 首先我们要判定传给我们的整数数组的长度大于1
• 其次就是，有些时候冒泡排序在排列的过程中，不需要冒泡那么多次，实际上数据已经达到了有序状态，需要加以判定

let arrTestAnotner = [12, 12, 89, 33, 6, 8, 99, 23];
function bubbleSortAnother(arrTestAnotner) {
  // 判断数组长度
  if(arrTestAnotner.length <= 1) {
    return;
  }
  // 定义一个变量用来保存数组长度，避免每次循环都计算一次
  let arrLength = arrTestAnotner.length;
  for (let i = 0; i < arrLength; ++i) {
    // 定义一个提前退出循环的标识
    let flag = false;

    // arrLength - i - 1这里多减去一个1，是为了避免内层循环越界
    for (let j = 0; j < arrLength - i - 1; ++j) {
      if (arrTestAnotner[j] > arrTestAnotner[j + 1]) {
        // 利用解构来赋值
        [arrTestAnotner[j], arrTestAnotner[j + 1]] = [
          arrTestAnotner[j + 1],
          arrTestAnotner[j]
        ];
        flag = true;
      }
    }
    
    // 如果内层循环了一圈都没数据交换，则表明确实是排好序了，所以结束外层循环
    if(!flag) break;
  }
}

bubbleSortAnother(arrTestAnotner);
console.log(arrTestAnotner);

输出结果：

Array(8) [6, 8, 12, 12, 23, 33, 89, 99]

插入排序

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

代码如下：

let arr = [12, 12, 89, 33, 6, 8, 99, 23];

function InsertionSort(arr) {
  let arrLength = arr.length;

  if(arrLength <= 1) {
    return;
  }

  // 我们把左边当作已排好的序列，右边当作没拍好的序列，每一次内循环下来就会做好一次左边部分的排序（升序）
  for (let i = 1; i < arrLength; i++) {
    // 选出一个值
    let value = arr[i];
    let j = i - 1;
    for(; j >= 0; j--) {
      if(arr[j] > value) {
        arr[j + 1] = arr[j]; 
      }else {
        break;
      }
    }
    arr[j + 1] = value;
  }
}

InsertionSort(arr);
console.log(arr);

输出结果：

Array(8) [6, 8, 12, 12, 23, 33, 89, 99]

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码如下：

let arr = [12, 12, 89, 33, 6, 8, 99, 23];

function SelectSort(arr) {
  let arrLength = arr.length;

  if(arrLength <= 1) {
    return;
  }

  for(let i = 0; i < arrLength - 1; i++) {
    // 定义一个变量用来保存找到的最大值或最小值的索引
    let index = i;
    for(let j = i + 1; j < arrLength; j++) {
      // 大于 升序，小于 降序
      if(arr[index] > arr[j]) {
        index = j;
      }
    }
    [arr[i], arr[index]] = [arr[index], arr[i]];
  }
}

SelectSort(arr);
console.log(arr);

输出结果为：

Array(8) [6, 8, 12, 12, 23, 33, 89, 99]