algorithms

[yanlee26]

insertSort

function insertSort(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i]; // 当前项
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]; // 如果前一项大于当前项 则把前一项往后挪一位
      preIndex-- // 用当前项继续和前面值进行比较
    }
    arr[preIndex + 1] = current; // 如果前一项小于当前项则 循环结束 则将当前项放到 前一项的后面
  }
  return arr;
}

selectSort

function selectSort(arr) {
  let len = arr.length;
  let temp = null;
  let minIndex = null;
  for (let i = 0; i < len - 1; i++) { // 把当前值的索引作为最小值的索引一次去比较
    minIndex = i; // 假设当前项索引 为最小值索引
    for (let j = i + 1; j < len; j++) { // 当前项后面向一次比小
      if (arr[j] < arr[minIndex]) { // 比假设的值还要小 则保留最小值索引
        minIndex = j; // 找到最小值的索引位置
      }
    }
    // 将当前值和比较出的最小值交换位置
    if (i !== minIndex) {
       temp = arr[i]
       arr[i] = arr[minIndex];
       arr[minIndex] = temp;
    }
  }
  return arr;
}

bubleSort

function bubleSort(arr) {
  let length = arr.length;
  let temp = null;
  for (let i = 0; i < length - 1; i++) { // 控制轮数
    let flag = false; // 当前这轮是否交换过标识
    for (let l = 0; l < length - i - 1; l++) { // 控制每轮比较次数
      if (arr[l] > arr[l + 1]) {
        temp = arr[l];
        arr[l] = arr[l + 1];
        arr[l + 1] = temp;
        flag = true; // 如果发生过交换flag则为true
      } 
    }
    if (!flag) { // 优化  如果从头到尾比较一轮后 flag依然为false说明 已经排好序了 没必要在继续下去
      temp = null;
      return arr;
    }
  }
}

quickSort

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let midIndex = Math.floor(arr.length / 2);
    let midNum = arr.splice(midIndex, 1)[0];
    let left = [];
    let right = [];
    for(let i = 0; i < arr.length; i++) {
        let cur = arr[i];
        if (cur <= midNum) {
            left.push(cur);
        } else {
            right.push(cur);
        }
    }
    return quickSort(left).concat(midNum, quickSort(right));
}