yangzheng93 / leetcode-practise Goto Github PK

export function insertSort (data) {
  for (let index = 1; index < data.length; index++) { // 从第二个开始遍历, data[0] 为初始有序序列
    let curIndex = index // cache current index

    while (data[curIndex - 1] !== undefined) { // 如果前一个元素存在
      if (data[curIndex - 1] > data[curIndex]) { // 当前元素大于后一个元素
        const temp = data[curIndex - 1]
        data[curIndex - 1] = data[curIndex]
        data[curIndex] = temp
        curIndex -= 1 // 前移一位
      } else {
        break
      }
    }
  }

  return data
}

export function insertSort (data) {
  for (let index = 1; index < data.length; index++) { // 从第二个开始遍历, data[0] 为初始有序序列
    const curValue = data[index] // cache current value

    for (let j = index; j >= 0; j--) {
      if (data[j - 1] > curValue) { // 当前比较元素小于前一个元素
        data[j] = data[j - 1] // 将前一个元素后移
      } else {
        data[j] = curValue // 若当前元素大于等于前面的元素, 则说明当前位置即为插入位置,且退出循环
        break
      }
    }
  }

  return data
}

export function insertSort (data) {
  for (let index = 1; index < data.length; index++) { // 从第二个开始遍历, data[0] 为初始有序序列
    const curValue = data[index] // cache current value

    let left = 0, right = index - 1 // 设置 left 和 right 为有序数组左右2个指针
    while (left <= right) {
      const mid = (left + right) >>> 1 // 取中位数
      if (data[mid] > curValue) {
        right = mid - 1 // 向左缩小区间
      } else {
        left = mid + 1 // 向右缩小区间
      }
    }

    // left 即为待插入的索引, 所以 left ~ (index - 1) 位置的所有元素后移, 空出待插入位置
    for (let i = index - 1; i >= left; i--) { // 将前面元素赋值给后面, 达到后移的目的
      data[i + 1] = data[i]
    }

    data[left] = curValue
  }

  return data
}

export function quickSort (data) {
  const len = data.length

  // 特殊处理
  if (len <= 1) {
    return data
  }

  const left = [];
  const right = [];// 设置左右数组

  // 取中间位为基准点进行划分, 最左和最右索引
  const pivotIndex = (0 + len - 1) >>> 1
  // 设置与基准点相等的数组
  const center = [data[pivotIndex]]

  for (let index = 0; index < len; index++) {
    if (index != pivotIndex) { // 基准点排除
      // 大于基准点的数丢到right，小于的丢到left，相等丢到center
      data[index] === data[pivotIndex]
        ? center.push(data[index])
        : (data[index] > data[pivotIndex]
            ? right.push(data[index])
            : left.push(data[index]))
    }
  }

  // 将左边数组，基准点数组，右边数组合并成最终结果
  return quickSort(left).concat(center, quickSort(right))
}

// 交换函数
function swap (data, l, r) {
  const temp = data[l]
  data[l] = data[r]
  data[r] = temp
  return data
}

// 将arr划分，一部分小于pivot，一部分大于pivot
function partition (arr, l, r) {
  const pivot = arr[r] // 设置最右边元素为基准
  let storeIndex = l

  for (let i = l; i < r; i++) {
    // 将小于 pivot 的元素通过交换，丢到 storeIndex 位置处
    if (arr[i] < pivot) {
      swap(arr, storeIndex, i)
      storeIndex += 1
    }
  }

  // 将 pivot 交换到 storeIndex 处，基准元素放到最终正确的位置上
  swap(arr, r, storeIndex)
  return storeIndex
}

function quickSort (data, left, right) {
  if (left < right) {
    const partitionIndex = partition(data, left, right)
    quickSort(data, left, partitionIndex - 1)
    quickSort(data, partitionIndex + 1, right)
  }

  return data
}