JS模拟数组操作(新增、删除、插入、排序、反转)

21,528 阅读2分钟

由于 js 没有 C 语言的指针,所以我们这里模拟数组只是模拟数组操作的思路。

由于本人水平有限,欢迎大家指正,看过能点个赞就更好了,谢谢大家。

先创建一个ArrayList类。

class ArrayList {
  list: any[]
  length: number
  constructor(list = []) {
    this.list = list
    this.length = list.length
  }
 }

新增(push)

从平时的使用中我们可知,数组的push方法是向数组最后一位添加元素,数组长度会变为this.length + 1,数组最后一位的数组下标为 this.length。所以我们的新增方法可以写成:

appendChild(item: any) {
    this.list[this.length] = item
    this.length++
 }

删除 (指定被删除元素的下标)

假定被删除元素下标为 i

  • 先找到需要被删除的元素 this.list[i]
  • 数组元素下标从i开始,this.list[i] = this.list[i + 1],元素被删除,后面所有元素向前进一位。
  • 修改数组长度
  • 返回被删除的元素
removeChild(index: number) {
    let removeItem = this.list(index)
    let length = this.length
    // 从被删除的元素开始向前移动
    for (let i = index; i < length - 1; i++) {
      this.list[i] = this.list[i + 1]
    }
    // 删除最后一个空位
    delete this.list[length - 1]
    this.list.length--
    this.length--
    return removeItem
  }

反转

  • 设定两个变量i,j,对应需要反转数组的头尾
  • 头尾进行互换, i++, j--
  • i >= j时,停止互换
  • 返回新数组
 // 反转
  inversion(arys = null) {
    let list = arys || this.list
    let length = list.length - 1
    // i 代表 头, j 代表尾部下标
    let i = 0, j = length - i, t: any;
    while (j > i) {
      t = list[i]
      list[i] = list[j]
      list[j] = t
      i++
      j--
    }
    return list
  }

插入

此方法有两个参数,插入位置的下标以及被插入的元素。

  • 获取数组长度
  • 把被插入位置的元素,统一往后移一位,先从最后一位开始移动 this.list[length] = this.list[length - 1]
  • 被插入位置插入元素
  • 修改数组长度
// 插入
  insert(index: number, item: any) {
    let length = this.length
    // 从最后一位依次移动元素至被插入下标前一位
    for (let i = length; i > index; i--) {
      this.list[i] = this.list[i - 1]
    }

    this.list[index] = item
    this.length++
    return true
  }

排序 (快排)

  • 找出被排序数组的基准值下标(找最中间一位,简化操作)
  • 根据下标找出基准值
  • 对数组进行循环,大于基准值数放到right数组,小于基准值数放到left数组
  • right、left数组,进行递归遍历排序
  • 输出left + 基准值 + right 组成的数组
 quicksort(arys, ) {
    const ary = arys.slice(0)
    if (ary.length <= 1) {
      return ary
    }
    // 基准值下标
    let pivotIndex = Math.floor(ary.length / 2);
    基准值
    let pivot = ary.splice(pivotIndex, 1);
    const left = [], right = [];

    for (let i = 0; i < ary.length; i++) {
        //当前元素大于基准值
      if (ary[i] > pivot) {
        right.push(ary[i])
      } else {
        left.push(ary[i])
      }
    }
    return this.quicksort(left).concat(pivot, this.quicksort(right))
  }

欢迎大家进行指导留言,谢谢大家点赞鼓励支持。