数组及原理

一、构造数组
- 1 - Array
- 2 - 转换数组
二、判断数组

一、构造数组

1 - Array

创建一个数组：new Array(item1,item2……)
字面量创建一个数组：let array = []

2 - 转换数组
Array.of

Array.from

let arr3 = Array.of("a","b");
let arr4 = Array.of(3);     // 把传进来的值作为数组的第一项
let arr5 = Array.from({0: 'a', 1: 'b', 2:'c', length: 3});
console.log(arr3) // [ 'a', 'b' ]
console.log(arr4) // [ 3 ]
console.log(arr5) // [ 'a', 'b', 'c' ]

二、判断数组

五种判断数组的方式：

API判断 - Array.isArray
instanceof 判断
原型判断
- Array.prototype.isPrototypeOf
- Object.getPrototypeOf
- Object.prototype.toString ```javascript let newArray = new Array(“a”); // 以下返回结果都为true let array1 = [1]; console.log(Array.isArray(newArray)); console.log(Array.isArray(array1));

console.log(newArray instanceof Array); console.log(array1 instanceof Array);

console.log(newArray.constructor === Array) console.log(array1.constructor === Array)

console.log(Array.prototype.isPrototypeOf(newArray)); Array.prototype.isPrototypeOf(array1);

console.log(Object.getPrototypeOf(newArray) === Array.prototype); console.log(Object.getPrototypeOf(array1) === Array.prototype);

console.log(Object.prototype.toString.call(newArray) === ‘[object Array]’); console.log(Object.prototype.toString.call(array1) === ‘[object Array]’);

<a name="Jp9QS"></a>
## 三、数组的API
<a name="KFeLM"></a>
### 1 - 会改变数组本身（9个）
主要为：增删改
- push/pop （新增/删除）
- unshift/shift （新增/删除）
- reverse （反转）
- sort （排序）
- splice （截取）
- copyWithin （复制）
- fill （填充）
```javascript
let originArray = ["Tom","July","Lily","VC"];
let pushData = originArray.push("PUSH");
console.log(pushData) // 5
console.log(originArray); // ["Tom","July","Lily","VC","PUSH"]
let popData = originArray.pop();
console.log(popData); // PUSH
console.log(originArray); //["Tom","July","Lily","VC"]
let unshiftData = originArray.unshift("UNSHIFT");
console.log(unshiftData); // 5
console.log(originArray); // ["UNSHIFT","Tom","July","Lily","VC"]
let shiftData = originArray.shift();
console.log(shiftData); // UNSHIFT
console.log(originArray); //["Tom","July","Lily","VC"]
let reverseData = originArray.reverse()
console.log(reverseData); // [ 'VC', 'Lily', 'July', 'Tom' ]
console.log(originArray); // [ 'VC', 'Lily', 'July', 'Tom' ]
let sortData = originArray.sort((a,b) => {return a-b});
console.log(sortData);  // [ 'VC', 'Lily', 'July', 'Tom' ]
console.log(originArray); // [ 'VC', 'Lily', 'July', 'Tom' ]
let spliceData = originArray.splice(0,3);
console.log(spliceData); // [ 'VC', 'Lily', 'July' ]
console.log(originArray);// [ 'Tom' ]
let copyWithin = originArray.copyWithin(0,3);
console.log(copyWithin);
console.log(originArray);
let fillData = originArray.fill(2,3,5);
console.log(fillData);
console.log(originArray);

2 - 不会改变数组本身（9个）

主要为：拼接、查找、转换

concat （拼接数组）
join （拼接数组）
slice （截取数组）
indexOf （从前向后查找数组）
lastIndexOf（从后向前查找数组）
includes （ES6新增查找数组）
toString （数组转换为字符串）
toLocaleString（数组转换为字符串）
flat（拉平数组） ```javascript // concat/join/slice/toString/toLocaleString/indexOf/lastIndexOf/includes/flat let originArr1 = [1,2,3]; let originArr2 = [3,5,4,5,6]; let concatData = originArr1.concat(…originArr2); console.log(concatData); // [ 1, 2, 3, 3, 5, 4, 5, 6 ]

let joinData = originArr2.join(“&”); console.log(joinData); // 3&5&4&5&6

let sliceData = originArr2.slice(1,4); console.log(sliceData); // [ 5, 4, 5 ]

let toString = originArr2.toString(); console.log(toString); // 3,5,4,5,6

let toLocaleString = originArr2.toLocaleString(); console.log(toLocaleString); // 3,5,4,5,6

let indexData = originArr2.indexOf(5); console.log(indexData); // 1

let lastIndexData = originArr2.lastIndexOf(5); console.log(lastIndexData); // 3

<a name="DSxW5"></a>
### 3 - 遍历数组（13个）
ES6新增 keys、values、entries、find、findIndex、flatMap
- forEach
- map
- some
- every
- filter
- reduce
- reduceRight
- keys
- values
- entries
- find
- findIndex
- flatMap
<a name="BJPbj"></a>
## 四、常见的排序算法
<a name="GkTgD"></a>
### 1 - 冒泡排序
> 冒泡排序是比较两个相邻的元素，将值大的元素交换到右边
```javascript
function bubbleSort(array) {
  let length = array.length;
  if (length < 2) return array;
  // 第一个循环控制要比较的趟数
  for (let i = 0; i < length; i++) {
    // 第二个循环是当前趟要比较的个数
    for (let j = 0; j < i; j++) {
      if (array[j] > array[i]) {
        let temp = array[j];
        array[j] = array[i];
        array[i] = temp;
      }
    }
  }
  return array;
}

2 - 快速排序

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quickSort(array) {
  let quick = function (arr) {
    if (arr.length <= 1) return arr;
    let index = Math.floor(arr.length / 2);
    let pivot = arr.splice(index, 1)[0];
    let left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < pivot) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return quick(left).concat([pivot], quick(right))
  }
  return quick(array);
}

3 - 插入排序

从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果符合条件则插入；然后在用第三个和第二个比较，符合条件插入，但是还得继续网签比较，直到不符合条件

function insertSort(array) {
  let len = array.length;
  let current, prev;
  for (let i = 1; i < len; i++) {
    current = array[i];
    prev = i - 1;
    while (prev >= 0 && array[prev] > current) {
      array[prev + 1] = array[prev];
      array[prev] = current
      prev--
    }
  }
  return array;
}

4 - 选择排序

每次循环获取到剩余位置的最小值的索引，交换位置

function selectSort(array) {
  let len = array.length;
  let minIndex;
  for (let i = 0; i < len; i++) {
    minIndex = i;
    for (let j = i; j < len; j++) {
      if (array[j] < array[i]) {
        minIndex = j
      }
    }
    let temp = array[minIndex];
    array[minIndex] = array[i];
    array[i] = temp;
  }
  return array;
}

5 - 归并排序

先把数组拆分成一定个数的有序小数组，然后把小数组合并

function mergeSort(array) {
  function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        result.push(left[leftIndex++])
      } else {
        result.push(right[rightIndex++])
      }
    }
    while (leftIndex < left.length) {
      result.push(left[leftIndex++])
    }
    while (rightIndex < right.length) {
      result.push(right[rightIndex++])
    }
    return result
  }
  const mergeSortInner = (array) => {
    if (array.length === 1) return array;
    let mid = Math.floor(array.length / 2);
    let left = array.slice(0, mid);
    let right = array.slice(mid, array.length);
    return merge(mergeSortInner(left), mergeSortInner(right))
  }
  return mergeSortInner(array)
}