第五天笔记 (数组)
数据结构
数据结构主要是数据的一个存储和逻辑结构的体现。只要能存储数据的一个结构我们就称为数据结构
存储结构
-
循序存储结构
随着数据量的增加时间复杂度增加
-
链式存储结构
-
索引存储结构
-
散列存储结构
存储最快
逻辑结构
线性结构
-
数组
-
队列
-
栈
非线性结构
-
链表
-
图
-
二叉树
-
散列表
-
广义表
-
······
相关知识点
-
数组 又被称为顺序表主要通过索引下标来进行访问(排序)
-
队列 先进先出的容器
-
栈 先进后出
-
树 二叉树
-
图 对应的指针的指向
-
链表 通过对应的指针来进行指向
-
散列表 hash表(hashcode来进行编码的)
-
······
数组
概述
数组是一种线性的数据结构,他可以存储对应的数据,一般通过对应的索引下标进行数据的访问。在一般情况下我们在数组里面存储的数据类型是一致的。 (数组也可以存储不同数据类型的数据)
数组的定义
使用[]赋值来定义
var arr=[]
var arr1=[1,2,3]
使用new关键字来定义
var arr=new Array()// 没有数据的数组
var arr1=new Array(10)// 单个参数表示数组长度
console.log(arr1)// 10个 empty(空)
var arr2=new Array(1,0,1,2,3)// 多个参数表示赋值
console.log([]==[])// false 数组是对象 对象比较的是地址
数组的特性
数组具备下标 可以通过下标来访问和赋值操作
数组具备length属性 可以赋值对数组进行扩容或删除(字符串的length属性是只读的)
var arr=[1,2,3,4,5]
console.log(arr[0])// 1 下标从0开始
arr[3]=18 // 通过下标赋值
console.log(arr[3])// 18
arr[10] = 20// 数组会自动扩容
console.log(arr[10])// 20
console.length(arr.length)// 通过length访问对应的长度 11 因为上面扩容到了11
数组的遍历
使用普通循环遍历
var arr=[1,2,3,4]
for(var i=0;i<arr.length;i++){
console.log(arr[i])
}
使用es5 for in 循环 (for in 循环是用来遍历对象的数组也是对象)
for in 循环遍历的是对象的key(数组的下标)
for(var index in arr){
console.log(arr[index])
}
使用for of 遍历 (专门遍历数组的)
for of 不能遍历对象 只能遍历数组(伪数组)Es6
for (var value of arr){
console.log(value)
}
for in 和 for of 的区别
for in 是用于遍历对象的 他遍历的是对象的key(es5)
for of是用于遍历数组的 他遍历的是数组的值(es6)
练习
将一个数组中的第二个元素和第三个元素进行位置互换
var arr = [1, 2, 3, 4]
var a
function fn(pos1, pos2) {
a = arr[pos2 - 1]// 将第二个值保存
arr[pos2-1] = arr[pos1-1]// 给第二个值赋值
// a = arr[pos2 - 1]
arr[pos1-1] = a// 给第一个值赋值
console.log(arr);
}
fn(2,3)
将数组[2,3,1,5,6,7,3]中的最大值和最小值的位置进行互换
function fn(arr){
function fn(arr){
// var max=arr[0];// 假设的最大的值
// var min=arr[0];// 假设的最小的值
var a=0,b=0 // 最大值和最小值的下标
for(var i=0;i<arr.length;i++){// 找最大值和最小值的下标
if(arr[a]<arr[i]){// 有比假设大的就赋值给max 用变量a记录其下标
// max=arr[i]
a=i
}
if(arr[b]>arr[i]){// 有比假设小的就赋值给min 并用变量b记录其下标
// min=arr[i]
b=i
}
}
// 互换
var m=arr[a];// 保存最大值
arr[a]=arr[b]// 将最小值赋值给最大值的位置
arr[b]=m // 将最大值赋值给最小值的位置
return arr;
}
console.log(fn([2,3,1,5,6,7,3]));
传入某个数组 返回第二大的数
function fn(arr){
// 最大值的下标
var max=0
// 第二大值的下标
var a=0
for(var i=0;i<arr.length;i++){
// 找出最大值的下标
if(arr[max]<arr[i]){
max=i
}
}
for(var i=0;i<arr.length;i++){
// 排除最大值找出第二大的值
if(arr[a]<arr[i] && max!=i &&a!=max){
a=i
}else if(a==0&&a==max){// 解决当第一个数为最大值的情况
a=1
}
}
return arr[a]
}
console.log(fn([1,2,3,4,5,6,7]));
//更优解
function fn(arr){
if(arr.length<2){
return arr[0]
}
// 得到最大值和第二大的值
var max=arr[0] > arr[1] ? arr[0] : arr[1]
var semax=arr[0] < arr[1] ? arr[0] : arr[1]
for(var i=2;i<arr.length;i++){
// 如果你比最大的值还大 将你记录为最大值 当前值变为第二大
if(arr[i] > max){
semax=max
max=arr[i]
}else{
// 如果你比最大值小 那么比较你和第二大的值
if(arr[i]>semax){
semax=arr[i]
}
}
}
return semax
}
console.log(fn([1,2,3,10,5,9,8]));
数组的相关方法
所有的存储空间都具备增删改查的方法
添加 (add push set)
push 添加到后面(返回完新的数组)
var arr=[1,2]
var newLength=arr.push(3) // 返回一个新的长度
console.log(newLength)// 3
console.log(arr)// [1,2,3]
unshift 添加到第一个(返回完新的数组)
var arr=[1,2]
var newLength=arr.unshift(3) // 返回一个新的长度
console.log(newLength)// 3
console.log(arr)// [1,2,3]
删除
delete(删除直接回收,硬删除) remove(删除完还在内存中,软删除) pop ···
pop 删除最后一个(返回删除的元素)
var arr=[1,3]
var newLength=arr.pop() // 返回的是删除的元素
console.log(newLength)// 3
console.log(arr)// [1]
shift 删除第一个(返回删除的元素)
var arr=[1,3]
var newLength=arr.shift() // 返回的是删除的元素
console.log(newLength)// 3
console.log(arr)// [3]
修改(replace set···)
覆盖
arr[0]==新的值
先删再加
splice 的应用
var arr = [1,2,3]
arr.splice(1,1,4)// 从下标为1开始删 1 个元素 再加上1个元素 4
splice 的删除和增加操作
var arr=[1,2,3]
// arr.splice(1)// 省略个数 删到最后
// arr.splice(1,3)// 删除指定的元素段这里是从下标1开始3结束包含1和3
// arr.splice(1,0,3)// 在第二个元素前添加元素
splice 返回的是删除的数据组成的数组
查询(select query get...)
indexOf 根据传入的值查询第一次出现的下标
根据索引查询(查询对应的索引) indexOf 传入对应的元素 返回对应的index(下标)(如果没有返回-1)
var arr[2,4,6,8]
console.log(arr.indexOf(4))// 1
console.log(arr.indexOf(10))// -1
// 从第三个数 从前往后数 第二个参数为查找左边(从左到右)
console.log(arr.indexOf(4,2))
简单实现indexOf
var arr = [2,4,6,8,4]
// 魔力实现indexOf
function myIndexOf(value,start){
if(value == undefined){
throw new Error('参数未传递')
}
// 如果没有传递start 那么应该为默认值0
if(start==undefined){
start=0
}
// 开始查询
for(var i=start;i<arr.length;i++){
if(arr[i]==value){
return i
}
}
return -1
}
console.log(myIndexOf(4))
lastindexOf(从右到左)
var arr=[2,4,6,8,4]
console.log(arr.lastindexOf(4))// 4
console.log(arr.lastindexOf(4,2))// 1
lastindexOf简单的实现
var arr = [2, 4, 6, 8, 4]
// 魔力实现indexOf
function myIndexOf(value, start) {
if (value == undefined) {
throw new Error('参数未传递')
}
// 如果没有传递start 那么应该为默认值
if (start == undefined ) {
start = arr.length
}else if(typeof start!='number'){
throw new Error('参数类型不正确')
}
// 开始查询
for (var i = start; i >=0; i--) {
if (arr[i] == value) {
return i
}
}
return -1
}
console.log(myIndexOf(4))
以上方法都会影响原本的数组
不影响原本数组的方法(一定右返回值)
数组的拼接 concat犯法
var arr1=[1,2]
var arr2=[3,4]
var concatArr=arr1.concat[arr2]
console.log(arr1)// [1,2]
console.log(arr2)// [3,4]
console.log(concatArr)// [1,2,3,4]
var con=arr1.concat(3)// concat也可以传入数组也可以传入对应的值
console.log(con)//[1,2,3]
slice 截取
var arr=[1,2,3,4,5,6]
var sliceArr=arr.slice()// 传入一个开始的下标 结束的下标(默认么有传入结束的下标截取到末尾 不包含结束下标)
console.log(sliceArr,arr)// 没有传个数从0截取到结尾
join将对应的数组转为字符串
var arr=[1,2,3,4,5,6]
var a=arr.join('a')// 分割的一定是字符串 默认为逗号
数组排序
// 影响原数组
// arr.sort()按accli码排序)
// 高阶函数用法 将函数作为参数的函数叫高阶函数
var newarr=arr.sort(function(a,b){
return a-b// 正序 b-a 就是倒序
})
数组反转
var arr=arr.reverse()//影响原数组 反转数组
排序算法
常用的排序算法时间复杂度都是O(n2)
-
冒泡排序(逐层冒泡)
-
选择排序(选择一个数跟其他的进行比较)
-
插入排序(在插入数据的时候的排序法)
-
希尔排序(快速插入排序)
-
快速排序(快速冒泡排序(数据量不大的情况下最快) )
-
归并排序(大数据处理中最快的排序)
-
堆排序
-
桶排序
冒泡排序O(n2)
前一个跟后一个比较 比较完就会交换位置 知道比较完他就完成了
//冒泡排序
function bubleSort(arr){
//冒泡排序 外层的轮数
for(var i=0;i<arr.length-1;i++){
//控制比较的次数
for(var j=1;j<arr.length-i;j++){
//j和j-1 俩俩进行比较
if(arr[j]<arr[j-1]){
//换位置
var temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
}
}
}
return arr
}
选择排序O(n2)
选择一个数和所有的数进行比较 如果比较完发现不是之前的那个数就换位置
// 选择排序
function fn(arr){
for(var i=0;i<arr.length-1;i++){
// 指定max为当前遍历的下标
var max=i
//max要跟其他的所有未排序比较
for(var j=i+1;j<arr.length;j++){
if(arr[max]<arr[j]){
max=j
}
if(max!=i){
var temp=arr[max]
arr[max]=arr[i]
arr[i]=temp
}
}
}
return arr
}
console.log(fn([1,2,3,4,5]));
快速排序(二分排序)O(nlogn)
快速排序就是无限二分 取一个中间值 比中间值大的放右边 比中间值小的放左边
function fn(arr){标签:arr,console,log,笔记,数组,var,下标,第五天 From: https://www.cnblogs.com/balloontrue/p/17111742.html
// 如果arr 只有1个或没有就直接返回这个数组
if(arr.length<=1){
return arr
}
var m=arr[0]
// 容器
var left=[],right=[]
for(var i=1;i<arr.length;i++){
// 无限得出小的在左边大的在右边
m<arr[i]?right.push(arr[i]):left.push(arr[i])
}
//利用递归 最后合并
return fn(left).concat(m).concat(fn(right))
}
console.log(fn([5,2,3,4,4]));