排序算法

冒泡排序

让数组的当前项和数组的后一项进行比较，如果当前项比后一项大，则两项交换位置（让大的靠后）即可

const arr = [12, 5, 56, 78, 90]
function bubbleSort(arr) {
  const len = arr.length - 1;
  let temp = null;
  // 外层循环控制比较次数
  for (let i = 0; i < len; i++) {
    let done = true; // 设置标记优化循环次数
    // 里层循环每一次比较次数
    for (let j = 0; j < len - i; j++) {
      // 如果前一项大于后一项，交换位置
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        done = false;
      }
    }
    if (done) {
      break;
    }
  }
  return arr;
}
console.log(bubbleSort(arr)); // [5, 12, 56, 78, 90]

插入排序

开始先抓一张牌
继续抓牌，抓到这张牌，和手里的牌依次比较（从后向前比较）
如果当前新牌A比手里的某张牌B大，则把A放到B的后面，如果小则继续向前面的牌比较（如果已经比较到第一张了，则把当前牌A插入到最前面即可）

const arr = [12, 5, 56, 78, 90]
function insertSort(arr) {
  // 1.定义新数组，用来存储抓到手里的牌
  const handleBrand = [];
  const len = arr.length;
  handleBrand.push(arr[0]); // 开始先抓一张牌进来
  // 2. 从第二项开始依次抓牌，一直到把台面上的牌抓光  
  for (let i = 1; i < len; i++) {
    // brand当前新抓的牌
    const brand = arr[i];
    const max = handle.length;
    // 和handle手里的牌依次比较（从后向前比较）  
    for (let j = max; j >= 0; j--) {
      const branded = handle[j]; // 每一次要比较的牌
      // 如果当前新牌brand比要比较的牌大，把brand放到branded后面  
      if (brand > branded) {
        handleBrand.splice(j + 1, 0, brand);
        break;
      }
      // 当前已经比到第一项，把新牌放到手中第一项即可
      if (j === 0) {
        handleBrand.unshift(brand);
      }
    }
  }
  return handleBrand;
}
console.log(insertSort(arr)); // [5, 12, 56, 78, 90]

快速排序

找到数组中间项，从数组中移除
让拿出的每一项和中间项继续比较
比中间项小的放在左边数组
比中间项大的放在右边数组
左右边数组继续重复上面操作（递归）
直至得到结果，左边 + 中间项 + 右边

const arr = [12, 5, 56, 78, 90]
function quickSort(arr) {
  // 当arr中小于等于一项，则不做处理
  if (arr.length <= 1) {
    return arr;
  }
  // 1. 找到中间项, 移除
  let middleIndex = Math.floor(arr.length / 2);
  const middleValue = arr.splice(middleIndex, 1)[0];
  // 2. 准备左右数组
  const arrLeft = [];
  const arrRight = [];
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (item < middleValue) {
      arrLeft.push(item);
    } else {
      arrRight.push(item);
    }
  }
  return quickSort(arrLeft).concat(middleValue, quickSort(arrRight));
}
console.log(quickSort(arr))// [5, 12, 56, 78, 90]

排序算法 ​

冒泡排序 ​

插入排序 ​

快速排序 ​

排序算法

冒泡排序

插入排序

快速排序