#算法
##大O表示法
用来描述计算机算法的效率，
数据项个数发生变化时，算法的效率也会跟着发生改变
### 常见的大O表示方法
| 符号 | 名称 |
| ---------- | -------------- |
| O(1) | 常数的 |
| O(log(n)) | 对数的 |
| O(n) | 线性的 |
| O(nlog(n)) | 线性和对数乘积 |
| O($n^2$) | 平方 |
| O($2^n$) | 指数的 |
当我们写一个算法的时候，其运行过程，并不是完全跟上面例子相同，它可能是个多项式，我们可以通过一些推导得出它们的大O表示法
### 推导成大O表示法
1、用常量1取代运行时间中所有的加法常量
2、在修改后的运行次数函数中，只保留最高阶项
3、如果最高存在且不为1，则去除与这个项相乘的常数
**举例**
1、如果得出的是一个常量，可以直接用上面第一条比如：76 用大O表示就是O(1)
2、如果得出的是多项式，比如：2N$^2$ + 3n + 1，根据上面第二条就等于 2N$^2$再根据第三条就等于O(N$^2$)
## 排序算法
**注意: 如果你在面试中不知道写什么排序算法好，尽可能写快速排序算法，在大部分情况下，快速排序是效率最高的**
排序算法有很多例如：冒泡、选择、插入、归并、计数、基数、希尔、堆、桶。
用三个简单排序和两个高级排序进行实例。
### 三个简单排序
#### 冒泡
#####思路
1、对未排序的的各个元素从头到尾依次比较相邻的两个元素大小关系
2、如果左边比右边的高，则两者交换位置
3、向右移动一个位置，比较后面两个
4、当走到最右边的时候，最高的一定被放在了最右边
5、按照这个思路，从左端重新开始，这次走到倒数第二个位置即可
6、依次类推就可以将数据排序完成
#####代码
```javascript
// 封装ArrayList
function ArrayList() {
this.array = []
ArrayList.prototype.insert = function (item) {
this.array.push(item)
}
ArrayList.prototype.toString = function () {
return this.array.join()
}
}
// 交换位置函数
ArrayList.prototype.swap = function (m, n) {
var temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
ArrayList.prototype.bubbleSort = function () {
// 1.获取数组的长度
var length = this.array.length
// 2.反向循环, 因此次数越来越少
for (var i = length - 1; i >= 0; i--) {
// 3.根据i的次数, 比较循环到i位置
for (var j = 0; j < i; j++) {
// 4.如果j位置比j+1位置的数据大, 那么就交换
if (this.array[j] > this.array[j+1]) {
// 交换
this.swap(j, j+1)
}
}
}
}
```
##### 效率
######根据N项数据的比较次数
是（N-1）+（N-2）+（N-3）+…+1 = N*(N-1)/2
推导成大O表示法N*(N-1)/2 = N$^2$/2-N/2，根据规则二变成N$^2$/2再根据规则三变成N$^2$
因此冒泡排序的比较次数大O表示法是O(N$^2$)
######根据N项数据的交换次数
是N*(N-1)/2（比较次数）／2结果是交换的次数，为什么除以2是因为如果有两次比较才需要交换一次（不可能每次比较都需要交换一次），那么就需要在比较次数的基础上再除以2，由于常量不包含在大O表示法中，因此我们可以认为交换次数的大O表示法也是O(N$^2$)
#### 选择
选择排序改进了冒泡排序，将交换次数由O(N$^2$)减少到了O(N)
但是比较次数依然是O(N$^2$)
##### 思路
1、选定第一个索引位置，然后和后面的元素依次比较
2、如果后面的项，小于第一个索引位置的项，则与第一个交换位置
3、经过第一轮的比较后，可以确定第一个位置的项是最小的
4、然后用同样的方式把剩下的项逐个比较
5、选择排序，第一轮会选出第一小的值，第二轮会选出第二小的值，直到最后
##### 代码
```javascript
ArrayList.prototype.selectionSort = function () {
// 1.获取数组的长度
var length = this.array.length
// 2.外层循环: 从0位置开始取出数据, 直到length-2位置
for (var i = 0; i < length - 1; i++) {
// 3.内层循环: 从i+1位置开始, 和后面的内容比较
var min = i
for (var j = min + 1; j < length; j++) {
// 4.如果i位置的数据大于j位置的数据, 记录最小的位置
if (this.array[min] > this.array[j]) {
min = j
}
}
this.swap(min, i)
}
}
```
##### 效率
###### 根据N项数据的比较次数
和冒泡排序的相同都是N*(N-1)/2
因此选择排序的比较次数大O表示法也是O(N$^2$)
###### 根据N项数据的交换次数
选择排序每次进行选择的时候，最多需要交换一次，一共遍历了N-1次
所以选择排序的交换次数用大O表示法是O(N)，所以选择排序在效率上通常是被认为高于冒泡排序的
####插入
插入排序是简单排序中效率最好的
##### 思路
###### 局部有序
1、插入排序的核心思想是局部有序
2、局部有序就好比一个队列中，我们选了一个作为标记的成员
3、被标记的左边成员已经是局部有序的
4、这意味着，有一部分人是按照顺序排列好的，有一部分人还是没有顺序
###### 插入排序的思路
1、从第一个元素开始，该元素可以被认为已经被排序
2、取出下一个元素，在已经排序的队列中从后向前扫描
3、如果该元素（已排序）的大于新元素，将该元素移到下一个位置
4、重复第三步骤，直到已经找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后，再重复上列步骤
##### 代码
```javascript
ArrayList.prototype.insertionSort = function () {
//获取数据长度
var length = this.arr.length;
// 第一次循环直接从第二项开始，第一项默认为已排序，结尾是长度-1项
for(var i = 1;i
