由于长时间工作原因，刚开始写代码时的一些简单算法和模式都已经忘了，记录一下

// 冒泡排序，就像小鱼在水里一个一个地把大泡泡往上冒
export function bubbleSort(arr: number[]): number[] {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

• 原理：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
• 代码流程：
  • 外层循环 for (let i = 0; i < len; i++) 控制排序的轮数，每一轮会将一个最大的元素 “冒泡” 到数组的末尾。
  • 内层循环 for (let j = 0; j < len - i - 1; j++) 用于比较相邻的元素。随着外层循环的进行，内层循环比较的范围逐渐缩小，因为每一轮已经将最大的元素放到了正确的位置。
  • if (arr[j] > arr[j + 1]) 用于判断相邻元素的大小，如果前一个元素大于后一个元素，则交换它们的位置。

------------------------------------------------

// 二分查找，如同在一本大字典里快速找单词
export function binarySearch(arr: number[], target: number): number {
  let left = 0
  let right = arr.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

• 原理：二分查找是一种在有序数组中查找特定元素的高效算法。它每次将搜索范围缩小一半，通过比较中间元素与目标元素的大小，决定继续在左半部分还是右半部分查找。
• 代码流程：
  • 初始化左右指针 left 和 right，分别指向数组的起始位置和结束位置。
  • 在 while (left <= right) 循环中，计算中间位置 mid。
  • 如果 arr[mid] === target，说明找到了目标元素，返回 mid。
  • 如果 arr[mid] < target，说明目标元素在右半部分，更新 left = mid + 1。
  • 如果 arr[mid] > target，说明目标元素在左半部分，更新 right = mid - 1。
  • 如果循环结束后仍未找到目标元素，返回 -1。

--------------------------------------------------------------------

// 快速排序，就像给数组来一场“分区大作战”
function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]
  let i = low - 1

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++
      const temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }

  const temp = arr[i + 1]
  arr[i + 1] = arr[high]
  arr[high] = temp

  return i + 1
}

export function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): number[] {
  if (low < high) {
    const pi = partition(arr, low, high)

    quickSort(arr, low, pi - 1)
    quickSort(arr, pi + 1, high)
  }
  return arr
}    

• 原理：快速排序采用分治法的思想，通过选择一个基准元素，将数组分为两部分，使得左边部分的所有元素都小于基准元素，右边部分的所有元素都大于基准元素，然后分别对左右两部分递归地进行排序。
• 代码流程：
  • partition 函数：
    • 选择数组的最后一个元素作为基准元素 pivot。
    • 使用变量 i 来记录小于基准元素的元素应该放置的位置。
    • 遍历数组，当遇到小于基准元素的元素时，将其与 i 位置的元素交换，并将 i 加 1。
    • 最后将基准元素放到 i + 1 位置，使得基准元素左边的元素都小于它，右边的元素都大于它。
    • 返回基准元素的最终位置。
  • quickSort 函数：
    • 如果 low 小于 high，说明数组还有元素需要排序。
    • 调用 partition 函数得到基准元素的最终位置 pi。
    • 递归地对基准元素左边的部分（low 到 pi - 1）和右边的部分（pi + 1 到 high）进行排序。
    • 最终返回排序好的数组。