【算法初探】数组、链表与选择排序

前端也要懂算法，阅《算法图解》有所得。

一、数组与链表

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;
}