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

风和日丽 2019-06-29

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

一、数组与链表

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

相关推荐