排序算法

冒泡排序

先找最大，从右到左

时间复杂度：O(n2)

空间复杂度：O(n)

思路：内层循环通过依次比较，将最大值放到最后面，在此基础上增加外部循环，每次外部循环都会排除已经完成排序的下标，再算出最大值，并放到排除已经排序的数组最后

/**
 * 冒泡排序
 * @param {Array} arr 
 * @returns 
 */
function bubbleSort(arr) {
  for (let j = 0; j < arr.length - 1; j++) {
    // 为什么循环体减1,因为循环体里面是当前的比较后一个,不减1,就会溢出
    // 减去j是为了减少无意义的循环次数
    for (let i = 0; i < arr.length - 1 - j; i++) {
      // 比较当前的与后一个大小,前面的大则换位子
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i]
        arr[i] = arr[i + 1]
        arr[i + 1] = temp
      }
    }
  }
  return arr
}

选择排序

先找最小，从左到右

时间复杂度：O(n2)

空间复杂度：O(n)

思路：内层循环每次找到最小的下标并放到数组最前面，再此基础上增加外部循环，外部循环每次以循环下标为坐标，寻找最小值换位到坐标中，一次完成排序

/**
 * 选择排序
 * @returns 
 */
function selectionSort() {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j
      }
    }
    if (indexMin != i) {
      // 最小值就是自己,不需要交换
      let temp = arr[i]
      arr[i] = arr[indexMin]
      arr[indexMin] = temp
    }
  }
  return arr
}

插入排序

从第二开始，依次从右到左开始比较最小值

时间复杂度：O(n2)

空间复杂度：O(n)

思路：从第二位开始，和前面的进行比较，如果前面的大于后面，则后面的等于前面的，继续向前找，如果找到了前面的小于后面都，则停止查找，覆盖该下标，如果到最开始都没有找到最小的，则将第一位变成比较值

/**
 * 插入排序
 * @param {*} arr 
 * @returns 
 */
function inSetrSort(arr) {
  // 从第二位开始
  for (let i = 1; i < arr.length; i++) {
    let j = i
    let temp = arr[j]
    while (j > 0) {
      if (temp > arr[j - 1]) {
        // 如果当前值大于前一个值,直接弹出,并且得知插入位置
        break
      }
      // 如果当前值小于前一个值,当前值就等于前一个字
      arr[j] = arr[j - 1]
      j--
    }
    // 在弹出的下标填入缓存的值
    arr[j] = temp
  }
  return arr
}

归并排序

难度较大，后续再看

快速排序

难度较大，后续再看

顺序搜索

在目标函数中寻找目标值，找不到则返回-1

时间复杂度：O(n)

function searchSort(list, carry) {
  return list.findIndex(e => e == carry)
}

二分搜索

针对有序数组的单项查找方法，找到会返回下标，未找到则返回-1，他的性能要高于顺序搜索，每次搜索都会将现有数组批成两半

时间复杂度：O(logN)

let bin = [1, 2, 3, 4, 5, 6, 7, 8, 9]

function binarySearch(list, carry) {
  let low = 0
  let high = list.length - 1
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    const ele = list[mid]
    if (carry > ele) {
      low = mid + 1
    } else if (carry < ele) {
      high = mid - 1
    } else if (carry == ele) {
      return mid
    }
  }
  return -1
}

console.log(binarySearch(bin, 1));