【算法初探】数组、链表与选择排序
一、数组与链表
1. 内存的原理：
相信我们经常会听到“堆”、“栈”之类的字眼，那么计算机的内存是什么呢？当我们去游泳时，我们需要将东西存在保险柜里，可能东西比较多，一个放不下，这时候就需要申请2个保险柜，再将东西放在柜子里，手里拿着开柜的钥匙。
计算机的内存分配亦是如此，当我们需要使用内存时，我们需要申请空闲内存，再将数据存入申请的内存里，最终得到存放数据的内存地址。如果我们需要访问一个数据，只需要知道数据存放的地址，就能访问。
2. 数组与链表
数组和链表是计算机最基础的2种数据结构。假如我们需要将5个数据放入内存中，那么计算机需要分给我们5个内存空间，那么使用数组和链表的区别是什么呢？
1）数组
如果使用数组存储，那么我们需要计算机分配5个相邻的内存空间，因为数组的每个元素都是有序且相邻的。此时，我们很容易发现，如果我需要往数组里插入一个元素，那么我们可能会面临如下困境：
- 相邻的内存被其他数据占用了。
- 计算机剩余的相邻内存长度不足以放下数组
如果使用链表来存储，以上问题将会迎刃而解。
2）链表
同样，以链表的形式存储5个元素，每个元素都记录着下一个元素的地址，那么只需要知道一个元素，就能得到整个链表，而不需要每个元素都相邻。
这样我们插入一个新元素，只需要改变上一个元素记录的地址。
当然，事情不会这么简单，数组与链表各有优劣。
3）优劣
上篇文章介绍了大O计数法表示一个算法的速度，那么我们来看看数组与链表插入、删除、和查找一个元素的速度：
数组 链表 查找 O(1) O(n) 插入 O(n) O(1) 删除 O(n) O(1)
显而意见，数组在查找操作上的性能较高，因为数组的每个元素都是相邻的，从而支持随机查找，即如果知道了第一个元素，那么第4个元素的位置也能猜到。相反，链表存储的数据则需要从头开始查找，因为只有前一个元素才知道后一个元素的位置。
同理： 对于插入和删除， 链表只需要修改上一个元素的地址，而数组如果插入的数据是中间的，则需要对后面所有的元素进行补位。
由此，很容易得出结论：
- 数组比较适合查询多，增删少的场景
- 链表多用于增删频繁而不需要经常查找的数据存储。
二、选择排序
1. 原理
选择排序的思想是，如果有一组数据需要从大到小排序，那么先找出最大的，移除，再在剩下的数中找第二大的，依次类推。其算法速度：O(n^2)
2. js实现
function selectionSort(myArray){
var len = myArray.length,
min;
for (i = 0; i < len; i++){
// 将当前位置设为最小值
min = i;
// 检查数组其余部分是否更小
for (j = i+1; j < len; j++){
if (myArray[j] < myArray[min]){
min = j;
}
}
// 如果当前位置不是最小值，将其换为最小值
if (i != min){
swap(myArray, i, min);
}
}
return myArray;
}
function swap(myArray, p1, p2){
var temp = myArray[p1];
myArray[p1] = myArray[p2];
myArray[p2] = temp;
}