数组，数组方法及排序算法（冒泡排序，选择排序，快速排序）

数组

数据结构

1.逻辑结构

2.存储结构：数据存储的结构方式

线性结构

• 数组（顺序表）
• 队列
• 栈
• 堆
• 链表

非线性结构

• 树
• 图
• hash（散列表）

（只要是能存数据的容器 就必须具备增删改查的方法）

3.算法

数组

数组概述：数组固定一类数据的组合（一般情况下数组里面的类型一致）（多个数据）

数组的核心

（为什么能遍历）数组是一个顺序表，对应依赖下标来实现的

数组的声明(引用数据类型)

1.使用[]声明数组

var arr = [1,2,3] //里面的数据用，分开
[1,2,3]==[1,2,3]  //fasle 引用数据类型比较地址
console.log(arr['0']) // 1 可以允许字符串
arr[0]=10   //可以赋值

2.使用new 关键词进行声明（对象）(单个参数表示长度 多个参数表示数据)

var arr = new Array（10）  //里面参数指定对应的长度 没写表示长度为0
console.log(arr1[0])   // undefined

length属性来访问对应的长度,也可以设置

var arr = new Array（）
console.log(arr.length)   // 0
arr.length=11   // 设置对应的长度
console.log(arr) 

数组元素随机给值

var arr = new Array（）
for（i=0;i<10;i++）{
    arr[i]=Math.random()  //0-1之间的随机数 包含0不包含1
}
console.log(arr)

数组遍历

传统for循环遍历

var arr=[1,2,3,4,56]
for（var i=0;ilength;i++）{ //利用顺序表的特点
    console.log(arr[i]) 

}

for in遍历（下标 迭代器 next方法）(对象遍历)

var arr=[1,2,3,4,56]
for（var index in arr）{ //index表示为下标
    console.log(arr[index])
}

注意：for in中的i变量类型是字符串，而不是数字类型，所以for in专门用来遍历对象，for in不会遍历空元素

for of遍历(迭代器来实现)（只能遍历数组）

var arr=[1,2,3,4,56]
for（var value of arr）{ //value表示的是里面的值
    console.log(value)
}

基础类型和引用类型

简单类型传递值，复杂类型传递地址

简单数据类型：number、string、boolean、undefined、null

复杂数据类型：Array、function, Object

其实函数也是一种类型：

function abc(){}
console.log(typeof abc); // function

值传递时将内存空间的值直接改变
代码：

var num = 11;
var num1 = num;
num = 20;
console.log(num); //20  引用传递时将值改变了，但是地址没有改变
console.log(num1)  //11

数组的方法

数组是一个存储结构（增删改查的操作）

添加（add push append）

栈方法（先进后出 后进先出）（有底无顶的容器）

push方法（添加到最后一个）

var arr = [1]
arr.push(10)    //返回值为长度
console.log(arr)  //[1,10]

队列方法（先进先出）（无顶无底的容器）

unshift方法（添加到第一个）

var arr = [1]
arr.unshift(10)   //返回值为长度
console.log(arr)  //[10,1]

删除（delete（硬删）remove（软删--可恢复））

栈方法

pop方法（删除最后面）

var arr =[1,2,3]
arr.pop()     //通过下标找 下标一般不写
//对应的返回值是被删除的那个值
console.log(arr)   //[1，2]
var arr =[1,2,3]和var arr =[4,5,6]不是一个东西

队列方法

shift方法（删除第一个）

var arr =[1,2,3]
arr.shift()   //通过下标找 下标一般不写
//对应的返回值是被删除的那个值
console.log(arr)   //[2，3]

修改（replace替换 update更新）

反转 reverse（将最后一个变到第一个 以此类推交换位置）

var arr= [1,2,3,4,5]
arr.reverse()  //返回反转后的数组（就是原本的数组）
console.log(arr)  //[5,4,3,2,1]
//arr.reverse和arr是一个东西

排序 sort（默认情况下是根据第一个字符的ACSII码进行排序）

var arr= [15,20,11,4,5]
arr.sort()  //返回排序后的数组（就是原本的数组）
console.log(arr)  //[11,15,20,4,5]
//arr.sort和arr是一个东西

sort 其实是一个高阶函数 高阶函数就是里面用函数做为参考的函数

var arr= [15,20,11,4,5]
arr.sort(function（a,b){
//1 和-1进行大小区分和排序规则
    return a-b  //a-b是正序  b-a是倒序
}  //返回排序后的数组（就是原本的数组）
console.log(arr)

concat slice（不会影响原本数组的方法 返回新的数组)

concat 连接 把多个数组变成一个数组返回 ... 扩展运算符（可以写多个）？（表示可写可不写）

//不会影响原本数组的方法 返回新的数组
var arr  = [1,2,3,4]
var arr1 = [1,2,3,4]
var arr2 = [1,2,3,4]
var arr3 = [1,2,3,4]
var newArr = arr.concat(arr1,arr2,arr3)//  打开数组取出里面的值
console.log(newArr);

slice 截取 把一个数组里面的东西提出 返回新的数组

var arr[1,2,3,4]
var sliceArr=arr.slice()  //不写参数全切
console.log（sliceArr） // [1,2,3,4]

var sliceArr1=arr.slice(0)  //从0开始切到最后 如果下标不存在返回一个空数组如arr.slice(10)
console.log（sliceArr1） // [1,2,3,4]

var sliceArr2=arr.slice(2,3)  //不包含3
console.log（sliceArr2） // [3]

contat方法slice方法返回的数组跟原本的数组不是一个对象 但是里面的值或者对象的地址是一样的（浅拷贝）

splice方法（会影响原来数组 可以删除 截取插入 ）

var arr=[12,13,45]
var newArr=arr.splice(0)   //从第一个开始删（全删）
console.log（newArr） //[12,13,45]
console.log（arr） //[]

 var newArr = arr.splice(1,3)
 //参数两个 开始位置 删除的个数（可写可不写 不写默认数组length） 操作后返回一个新的数组
    console.log(newArr) //[13,45,1]      
    console.log(arr) //[12,2,3]

 var newArr = arr.splice(1,0，3)
 console.log(newArr) //[12，3，13，45] 

排序算法

• 冒泡排序(最基础的排序) O(n^2)

  比较的趟数为（lenght-1）

  每一趟比较（length-i）次

  外层i循环为躺数

  内层j循环为每趟比较的次数

  var arr = [12, 4, 8, 3, 56, 34, 26]
  
          function bubble(arr) {
              for (i = 1; i < arr.length; i++) {
                  for (j = 0; j < arr.length - i; j++) {
                      if (arr[j] > arr[j + 1]) {
                          var temp = arr[j]
                          arr[j] = arr[j + 1]
                          arr[j + 1] = temp
                      }
                  }
              }return arr
          }
          console.log(bubble(arr));
  

• 选择排序（选择最大值的下标或者最小值的下标进行比较的排序）O(n^2)

  function selecter(arr){
  //遍历数组
  for(var i=0;ilength;i++){
  var min = i //记录最小下标 默认当前的i
  for(var j=i+1;jlength;j++){ //遍历后面的内容
  //如果当前值比最小值还小
  if(arr[j]//记录一下这个下标
  min = j
  }
  }
  //判断当前最小下标是否为开始的默认下标 不是就换位置
  if(min!=i){
  //换位置
  var temp = arr[min]
  arr[min] = arr[i]
  arr[i] = temp
  }
  }
  return arr
  }
  

• 快速排序（在数据量不多时最快 冒泡排序的进阶）O(nlogn)

  function quick(arr){
  if(arr.length<=1){
  return arr
  }
  //定义左边数组 右边数组 基数
  var left = [],right = [] ,mid=arr[0]
  //遍历数组
  for(var i=1;ilength;i++){
  arr[i]>mid?right.push(arr[i]):left.push(arr[i])
  }
  return quick(left).concat([mid],quick(right))
  }
  

• 希尔排序（插入排序的进阶）

• 插入排序（插入数据的时候排序）

• 归并排序（大数据排序的常用排序方法）

• .......