由于 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))
}
欢迎大家进行指导留言,谢谢大家点赞鼓励支持。