JavaScript--数组

一、数组的概念

数组是一种类列表对象，它的原型中提供了遍历和修改元素的相关操作。JavaScript 数组的长度和元素类型都是非固定的。

二、数组的声明

1、使用 Array 构造函数

let colors = new Array();

1）如果知道数组中元素的数量，那么可以给构造函数传入一个数值，然后 length 属性就会被自动创建并设置为这个值。

let colors = new Array(20);

2）也可以给 Array 构造函数传入要保存的元素。

let colors = new Array("red", "blue", "green");

3）在使用 Array 构造函数时，也可以省略 new 操作符。

let colors = Array(3); // 创建一个包含 3 个元素的数组
let names = Array("Greg"); // 创建一个只包含一个元素，即字符串"Greg"的数组

2、使用数组字面量（array literal）表示法

数组字面量是在中括号中包含以逗号分隔的元素列表。

let colors = ["red", "blue", "green"]; // 创建一个包含 3 个元素的数组
let names = []; // 创建一个空数组
let values = [1,2,]; // 创建一个包含 2 个元素的数组

三、数组的索引

1）要取得或设置数组的值，需要使用中括号并提供相应值的数字索引，在中括号中提供的索引表示要访问的值。

let colors = ["red", "blue", "green"]; // 定义一个字符串数组
alert(colors[0]); // 显示第一项
colors[2] = "black"; // 修改第三项
colors[3] = "brown"; // 添加第四项

2）数组中元素的数量保存在 length 属性中，这个属性始终返回 0 或大于 0 的值，如下例所示：

let colors = ["red", "blue", "green"]; // 创建一个包含 3 个字符串的数组
let names = []; // 创建一个空数组
alert(colors.length); // 3 
alert(names.length); // 0

3）通过修改 length 属性，可以从数组末尾删除或添加元素。

let colors = ["red", "blue", "green"]; // 创建一个包含 3 个字符串的数组
colors.length = 2; 
alert(colors[2]); // undefined

4）如果将 length 设置为大于数组元素数的值，则新添加的元素都将以undefined 填充，如下例所示：

let colors = ["red", "blue", "green"]; // 创建一个包含 3 个字符串的数组
colors.length = 4; 
alert(colors[3]); // undefined

5）使用 length 属性可以方便地向数组末尾添加元素，如下例所示：

let colors = ["red", "blue", "green"]; // 创建一个包含 3 个字符串的数组
colors[colors.length] = "black"; // 添加一种颜色（位置 3）
colors[colors.length] = "brown"; // 再添加一种颜色（位置 4）

数组中最后一个元素的索引始终是 length - 1，因此下一个新增槽位的索引就是 length。每次在数组最后一个元素后面新增一项，数组的 length 属性都会自动更新，以反映变化。

四、数组的遍历

1、传统的for循环遍历

var arr = [1,2,3,45,12]
//利用顺序表的特点 有序
for(var i=0;i<arr.length;i++){
console.log(arr[i])
}

2、for in遍历 (对象 下标 迭代器 next)

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

3、for of进行遍历（数组 迭代器来实现的）

//使用for of遍历(只能遍历数组)
for(var value of arr){ //value表示的是里面值
console.log(value)
}

五、数组的方法

1、栈方法

数组对象可以像栈一样，也就是一种限制插入和删除项的数据结构。栈是一种后进先出（LIFO，Last-In-First-Out）的结构，也就是最近添加的项先被删除。数据项的插入（称为推入，push）和删除（称为弹出，pop）只在栈的一个地方发生，即栈顶。

1）push()方法

push()方法接收任意数量的参数，并将它们添加到数组末尾，返回数组的最新长度。

let colors = new Array(); // 创建一个数组
let count = colors.push("red", "green"); // 推入两项
alert(count); // 2

2)pop()方法

pop()方法则用于删除数组的最后一项，同时减少数组的 length 值，返回被删除的项。

let colors = new Array("red","green"); // 创建一个数组
let item = colors.pop(); // 取得最后一项
alert(item); // red 
alert(colors.length); // 1

2、队列方法

队列以先进先出（FIFO，First-In-First-Out）形式限制访问。队列在列表末尾添加数据，但从列表开头获取数据。

1）push()方法

push()方法接收任意数量的参数，并将它们添加到数组末尾，返回数组的最新长度。

2）shift()方法

shift()方法删除数组的第一项并返回它，然后数组长度减 1。

let colors = new Array(); // 创建一个数组
let count = colors.push("red", "green"); // 推入两项
alert(count); // 2 

count = colors.push("black"); // 再推入一项
alert(count); // 3 

let item = colors.shift(); // 取得第一项
alert(item); // red 
alert(colors.length); // 2

3）unshift()方法

顾名思义，unshift()就是执行跟 shift()相反的操作：在数组开头添加任意多个值，然后返回新的数组长度。

let colors = new Array(); // 创建一个数组
let count = colors.unshift("red", "green"); // 从数组开头推入两项
alert(count); // 2 
count = colors.unshift("black"); // 再推入一项
alert(count); // 3

3、排序方法

1）reverse()方法

顾名思义，reverse()方法就是将数组元素反向排列。

let values = [1, 2, 3, 4, 5]; 
values.reverse(); 
alert(values); // 5,4,3,2,1

2）sort()方法

默认情况下，sort()会按照升序重新排列数组元素，即最小的值在前面，最大的值在后面。为此，sort()会在每一项上调用 String()转型函数，然后比较字符串来决定顺序。即使数组的元素都是数值，也会先把数组转换为字符串再比较、排序。

let values = [0, 1, 5, 10, 15]; 
values.sort(); 
alert(values); // 0,1,10,15,5

为此，sort()方法可以接收一个比较函数，用于判断哪个值应该排在前面。

比较函数接收两个参数，如果第一个参数应该排在第二个参数前面，就返回负值；如果两个参数相等，就返回 0；如果第一个参数应该排在第二个参数后面，就返回正值。

var arr3 = [15,20,11,4,5]
arr3.sort(function(a,b){
//1 和 -1来进行大小区分和排序规则
return b-a //a-b是正序 b-a就倒序
})
console.log(arr3);

4、操作方法

1）concat()方法

concat()方法可以在现有数组全部元素基础上创建一个新数组。它首先会创建一个当前数组的副本，然后再把它的参数添加到副本末尾，最后返回这个新构建的数组。如果传入一个或多个数组，则 concat()会把这些数组的每一项都添加到结果数组。如果参数不是数组，则直接把它们添加到结果数组末尾。

let colors = ["red", "green", "blue"]; 
let colors2 = colors.concat("yellow", ["black", "brown"]); 

console.log(colors); // ["red", "green","blue"] 
console.log(colors2); // ["red", "green", "blue", "yellow", "black", "brown"]

2） slice()方法

slice()用于创建一个包含原有数组中一个或多个元素的新数组。slice()方法可以接收一个或两个参数：返回元素的开始索引和结束索引。如果只有一个参数，则 slice()会返回该索引到数组末尾的所有元素。如果有两个参数，则 slice()返回从开始索引到结束索引对应的所有元素，其中不包含结束索引对应的元素。记住，这个操作不影响原始数组。

let colors = ["red", "green", "blue", "yellow", "purple"]; 
let colors2 = colors.slice(1); 
let colors3 = colors.slice(1, 4); 

alert(colors2); // green,blue,yellow,purple 
alert(colors3); // green,blue,yellow

注意： 如果 slice()的参数有负值，那么就以数值长度加上这个负值的结果确定位置。比如，在包含 5 个元素的数组上调用 slice(-2,-1)，就相当于调用 slice(3,4)。如果结束位置小于开始位置，则返回空数组。

3）splice()

splice()的主要目的是在数组中间插入元素，但有 3 种不同的方式使用这个方法，会影响原数组。

删除：需要给 splice()传 2 个参数：要删除的第一个元素的位置和要删除的元素数量。可以从数组中删除任意多个元素，比如 splice(0, 2)会删除前两个元素。

插入：需要给 splice()传 3 个参数：开始位置、0（要删除的元素数量）和要插入的元素，可以在数组中指定的位置插入元素。第三个参数之后还可以传第四个、第五个参数，乃至任意多个要插入的元素。比如，splice(2, 0, "red", "green")会从数组位置 2 开始插入字符串"red"和"green"。

替换：splice()在删除元素的同时可以在指定位置插入新元素，同样要传入 3 个参数：开始位置、要删除元素的数量和要插入的任意多个元素。要插入的元素数量不一定跟删除的元素数量一致。比如，splice(2, 1, "red", "green")会在位置 2 删除一个元素，然后从该位置开始向数组中插入"red"和"green"。

注意：splice()方法始终返回这样一个数组，它包含从数组中被删除的元素（如果没有删除元素，则返回空数组）。

let removed = colors.splice(0,1); // 删除第一项
alert(colors); // green,blue 
alert(removed); // red，只有一个元素的数组

removed = colors.splice(1, 0, "yellow", "orange"); // 在位置 1 插入两个元素
alert(colors); // green,yellow,orange,blue 
alert(removed); // 空数组

removed = colors.splice(1, 1, "red", "purple"); // 插入两个值，删除一个元素
alert(colors); // green,red,purple,orange,blue 
alert(removed); // yellow，只有一个元素的数组

六、排序算法

1、冒泡排序

冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

//冒泡排序核心点 俩个for循环嵌套 第一个躺数 相当于length-1 第二个每躺比较是递减
//相邻的俩个相比 j和j+1相比
function bubble(arr){
//遍历数组
for(var i=1;i<arr.length;i++){
//判断对应的没有比较的值
for(var 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
}

首先，声明一个名为 length 的变量，用来存储数组的长度（行{1}）。这一步可选，它能帮助我们在行{2}和行{3}时直接使用数组的长度。接着，外循环（行{2}）会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序（应该是数组中每项都经过一轮，轮数和数组长度一致）。然后，内循环将从第一位迭代至倒数第二位，内循环实际上进行当前项和下一项的比较（行{4}）。如果这两项顺序不对（当前项比下一项大），则交换它们（行{5}），意思是位置为j+1 的值将会被换置到位置 j 处，反之亦然。不推荐该算法，它的复杂度是 O(n2)。

2、选择排序

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

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

选择排序同样也是一个复杂度为 O(n2)的算法。和冒泡排序一样，它包含有嵌套的两个循环，这导致了二次方的复杂度。

3、快速排序

快速排序也许是最常用的排序算法了。它的复杂度为 O(nlog(n))，且性能通常比其他复杂度为 O(nlog(n))的排序算法要好。和归并排序一样，快速排序也使用分而治之的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开）。

快速排序比目前学过的其他排序算法要复杂一些。让我们一步步地来学习。

(1) 首先，从数组中选择一个值作为主元（pivot），也就是数组中间的那个值。
(2) 创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分（partition）操作。
(3) 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序

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