算法入门

一.算法的定义

任何代码片段都可以被称作是算法,这也就是说算法其实就是完成一组任务的指令.算法的优点在于要么速度很快,要么解决一些很有趣的问题,要么兼而有之.并且算法可以应用于任何编程语言中.

二.什么人适合学算法

学算法的人必须要懂得一定的数学知识,具体点就是线性代数的知识.只要你能做出这样一道题,那么恭喜你,可以学算法.

f(x) = x * 10;f(5) = ?;

三.二分查找

假设存在一个有序列表,比如1,2,3...100.如果我要你猜测我心中所想的数字是这个有序列表中的哪个数字,你会怎么猜呢?

最简单的办法就是从1到100挨着猜,这样一算,那么很明显,假如我想的是数字100,你有可能就要猜100次.如此一来,岂不是很浪费时间.

那么,同样的道理,如果在一行有100个字符的字符串中查找某个字母,你是不是也要查找100次呢?

其实有更快速的办法,就第一个例子而言,试想,如果我们第一次就把100拆一半,也就是50,然后猜测50,根据我的回答来做下一步的确定.也许我回答小了,那么猜测的范围就会在50到100之间了,如果是大了,那么猜测的范围也就到了1到50之间,依次类推,我们把每次猜测都分成一半,即100 -> 50 -> 25 -> 13->7->4->2->1,如此一来,我们最多猜7次就能猜中我心中想的数字.

像这样的把元素分一半来查找就叫 二分查找 .而通过二分查找实现的算法就叫 二分算法 ,简称 二分法 .

一般地,我们把包含n个元素的列表,用二分查找最多需要 log2^n 步.

也许你可能不记得对数的概念了,但你应该记得幂的概念.而对数log10^100相当于将多少个10的乘积结果为100.答案自然是2个,即10*10=100.因此log10^100 = 2;

总的来说,对数就是幂运算的逆运算.

仅当列表有序的时候,我们才可以用二分法来进行查找吗?那倒不一定,其实我们可以将这些列表的元素存储在一个数组中,就好像,我们把一个东西放在桶里一样,然后给这些桶标上顺序,而顺序则是从0开始编号的,第一个桶是0,第二个桶是1,依次类推.

比如有这样一个有序数组[1,2,3...100];我想要查找75这个数字的索引,很明显75这个数字对应的索引就是74.我们可以使用二分法编写代码,如下(这里以JavaScript代码为例,其它语言的代码也可以的):

var arr = [];
for(var i = 1;i <= 100;i++){
    arr.push(i);
}
var checknum = 75;
//定义第一个索引与最后一个索引
var low = 0;
var high = arr.length - 1;
//我们查找数字只能在两者之间查找,使用循环,只要范围没有缩小到只剩一个元素,都可以继续使用二分法拆成一半来查找
while(low <= high){
    //索引取一半,如果不是整数则向下取整
    var center = Math.floor((low + high) / 2);
    //最终结果一定是索引所对应的元素
    var result = arr[center];
    //判断结果是否等于想要的结果
    if(result === checknum ){
        console.log(center);
    }else if(result < checknum){
            //如果取得索引对应元素值小于猜的值,则修改最低索引的值,以缩小猜测范围
            low = center + 1;
    }else if(result > checknum){
            //如果取得索引对应元素值大于猜的值,则修改最大索引的值,以缩小猜测范围
            high = center - 1;  
    }else{
        console.log(null);
    }
}

得出最终结果就是74.

我以如下图来展示上例代码的算法:

因此我们可以封装成一个函数,传入参数就是一个数组和数组元素对应的值.如下:

function  getArrIndex(arr,result){
    var low = 0,high = arr.length - 1,center = Math.floor((low + high) / 2);
    while(low <= high){
        if(arr[center] === result){
            return center;
        }else if(arr[center] < result){
            low = center + 1;
        }else if(arr[center] > result){
            high = center - 1;
        }else{
            return '没有这个索引值';
        }  
    } 
}
//测试
getArrIndex([1,4,6,8,10],6);//2

四.大O表示法

在算法入门之一中,我总结到二分算法,并且在二分算法中也提到过运行时间.一般说来,我们在写程序时都会选择效率最高的算法,以最大限度的减少运行时间或者占用空间.

前面二分算法中说到,如果挨着简单的查找从1到100的列表,最多需要猜测100次,如果列表的长度更大呢?比如是1亿,那我们就要猜测1亿次.换句话说,最多需要猜测的次数与列表长度相同,这样所用到的时间,我们称之为 线性时间 .

而二分查找则不同,100次我们仅需猜测log2^100 ≈ 7次.而如果是1亿,我们也只需猜测log2^100000000 ≈ 26次.这样通过二分查找所需要的时间,我们称之为 对数时间 .

我们可以利用一种特殊的表示法来表示这种运行时间,即 大O表示法 .大O表示法指出算法的速度有多快.

在了解什么是大O表示法之前,我们先来看一个例子:

假设有100个元素的列表,我们使用二分查找大约需要7次(因为log2^100≈7),如果每一次大约为1毫秒.二分查找就需要7毫秒,而简单查找呢?简单查找就需要100毫秒,大约是二分查找的15倍左右.

那么假如有1亿个元素的列表呢,使用简单查找就是大约1亿毫秒,而二分查找则需要26毫秒(log2^100000000)左右就可以了.如此一来,简单查找比二分查找慢的多,而且简单查找足足是二分查找的将近400万倍.

这说明一个什么问题呢?

这说明算法的运行时间是以不同的速度增加的,也就是说随着元素的增多,二分查找所需要的额外时间并不多,而简单查找却要多很多.我们把这种情况称之为增速.仅仅知道算法的运行时间是不行的,我们还需要知道运行时间随着列表的增加而增加,即增速,大O表示法的用武之地就在于此.

一般的,拥有n个列表,简单查找需要执行n次操作,我们用大O表示法表示为O(n).当然单位不一定是毫秒或者秒,大O表示法也就指出了算法的增速.而使用二分查找,我们可以表示为O(log2^n).

再比如一个示例:假设我们要画一个16X16的网格图,简单查找就是一个一个的画,结果需要画256次.而如果我们把一张纸对折,再对折,再对折,再对折,每对折一次,格子数就会增加,对折一次画一次,如此一来,顶多需要log2^256,也就是8次就可以画出来.

我们用大O表示法,就可以表示成:简单查找为 O(n)的运行时间 ,而 O(log2^n) 则是二分查找所需时间.

大O表示法指出了最糟情况下的时间.什么意思呢?再看一个示例:

如果你要在一本书中使用简单查找查找一篇文章,所需要的时间就是O(n).这意味着在最糟糕的情况下,必须查找一本书中的每一页.如果要查找的文章刚好在第一页,一次就能找到,那么请问简单查找的运行时间是O(1)还是O(n)呢?

答案自然是O(n)呢.因为大O表示法指出了最糟糕情况下的运行时间.如果只用1次就能翻到,那这是最佳情况.

从这些案例当中,我们得出了如下结论:

1.算法的速度指的并非时间,而是增速 。

2.谈论算法的速度时,我们应该说的是随着速度的增加,运行时间将以什么样的速度增加 。

3.算法的运行时间用大O表示法表示 。

4.O(log2^n)比O(n)快,当搜索的元素越多,前者快的越多 。

事实上,还有另一种算法.即O(!n).也就是 阶乘算法 。来看一个案例:假如一个人要去4个城市旅行,并且还要确保旅程最短.利用排列与组合的知识得出,前往4个城市大约需要执行24次操作,而如果是5个城市,则大约需要执行120次操作.也就是说随着城市的增加,大约需要执行!n次操作.虽然这确实是一种算法,但这种算法很糟糕。

五.选择 排序 算法

在理解选择 排序算法 的原理之前，我们需要了解大O表示法，数组与链表等概念。

经常与计算机接触，相信都会听到内存这一个词，那么何为内存呢？我们用一个很形象的比喻来说明这个问题。

假设有一个柜子，柜子有很多抽屉，每个抽屉能放一些东西。也就是说，当我们往抽屉里放东西的时候，柜子就保存了这些东西。一个东西放一个抽屉，两个东西放两个抽屉。计算机内存的工作原理就如此，计算机的内存更像是许多抽屉的集合。

需要将数据存储到计算机中，你会请求计算机提供存储空间，然后计算机就会给你一个存储地址。在存储多项数据的时候，有两种数据结构，计算机可以存储，那便是数组和链表。

数组就是一系列元素的列表集合。比如，你要写一个待办事项的应用程序（前端术语也可以说是todolist）。那么你就需要将许多待办事项存储到内存中。使用数组意味着内存是紧密相连的，为何如此说呢？

数组的元素自带编号，每个元素的位置，我们也叫做索引。例如:

[10,20,30,40]这一个数组，元素20的索引或者说所处的位置是1。因为数组的编号都是从0开始的，这可能会让很多新手 程序员 搞不明白。几乎所有编程语言对数组的编号都是从0开始的，绝对不止JavaScript这一门语言。

假设，你要为以上[10,20,30,40]再添加一个元素，很明显，利用JavaScript提供的数组方法，你只能在之前或者最末又或者中间插入元素。但在内存中却不是这样。还是用一个比喻来说明。

相信每个人都有看电影的经历，试想当你到了电影院之后，找到地方之后就坐下，然后你的朋友来了，本想靠着你坐，但是靠着你的位置都被人占领了。你的朋友就不得不转移位置，在计算机中，请求计算机重新分配一个内存，然后才能转移到另一个位置。如此一来，添加新元素的速度就会很慢。

那么，有没有办法解决呢？

似乎，很多人都这样做过，由一个人占领位置之后，然后把旁边的预留座位也给占领，不仅仅是在电影中，在公交车上抢座位也是如此。这种办法，我们暂且称之为"预留座位"。

这在计算机中也同样适用。我们在第一次请求计算机分配内存的时候，就请求计算机分配一些空余的内存，也就是"预留座位"出来。假定有20个"预留座位"，这似乎是一个不错的措施。但你应该明白，这个措施，也存在缺点:

你额外请求的位置有可能根本就用不少，还将浪费内存。比如你选了座位，结果你的朋友没有来，其他人也不知道你的朋友不会来，也就不会坐上去，那么这个座位就空下来了。

如果来的人超过了20个之后，你预留的座位又不够，这就不得不继续重新请求转移。

针对这种问题，我们可以使用链表来解决。

链表也是一种数据结构，链表中的元素可存储在内存的任何地方。并且链表中 每一个元素都存储了下一个元素的地址，从而使一系列随机的内存串联在一起。

这就好像一个扫雷游戏，当你扫中一个，这个就会提醒你的四周格子有没有地雷，从而好作判断，让你是否选择点击下一个格子。因此，在链表中添加一个元素很容易：只需要将元素放入内存，并将这个元素的内存存储地址放到前一个元素中。

而且，使用链表还不用移动元素。因为只要有足够的内存空间，计算机就能为链表分配内存。比如如果你要为数组分配100个位置，内存也仅有100个位置，但元素不能紧靠在一起，在这样的条件下，我们是无法为数组分配内存的，但链表却可以。

链表好像自动就会说，“好吧，我们分开来坐这些位置”。

但链表也并非没有缺点。我们再做一个比喻：

假如你看完了一本小说的第一章觉得第一章不好看，想跳过几章去看，但并没有这样的操作，因为一般都是下一章下一章的看的，这意味着你要看第五十章，就要点下一章49次，这样真的很烦。（点目录不算）

链表也正是存在这一个问题，你在读取链表的最后一个元素时，你需要先读取上一个元素的存储地址，然后根据上一个元素的地址来读取最后这个元素。如果你是读取所有的元素，那么链表确实效率很高，但如果你是跳跃着读取呢？链表效率就会很低。

这也正是链表的缺点所在。但数组就不同，因为数组有编号，意味着你知道数组每个元素的内存地址，你只需要执行简单的数学运算就能推算出某个元素的位置。

利用大O表示法，我们可以表示将数组和链表的运行时间表示出来，如下:

数组   链表
读取: O(1)    O(n)
插入: O(n)    O(1)

其中O(1)称作常量时间，O(n)则是线性时间。

如果你要删除元素呢？链表显然也是更好的选择，因为你只需要修改前一个元素指向的地址即可。

那么问题来了，数组与链表究竟哪种数据结构用的最多呢？

要看情况。但数组显然用的更多，因为数组支持随机访问。元素的访问有两种方式：顺序访问与随机访问。顺序访问意味着 你需要挨着顺序一个一个的访问元素，而随机访问这不必如此。因为数组有编号，所以在随机访问上，数组更能体现它的优势。

有了前面的知识，现在，咱们来学习选择排序算法吧！

假设你的计算机存储了一些视频，对于每个视频的播放次数，你都做了记录，比如:

视频1:50

视频2:35

视频3:25

视频4:55

视频5:60

现在，你要做的就是将播放次数从少到多按顺序排列出来。该如何做呢？

首先，你肯定需要遍历这个列表，找出播放次数最少的，然后添加到新的一个列表中去，并将这个添加的元素在原来列表中删除，然后，你再次这样做，将播放次数第二少的找出来，依次类推……

最后，你就会得到一个有序列表

视频3:25

视频2:35

视频1:50

视频4:55

视频5:60

编写代码如下:

//用一个数组表示播放次数即可
var arr = [50,35,25,55,60];
// 编写一个函数，参数传入排序的数组
function selectSort(arr){
    //获取传入数组的长度
    var len = arr.length;
    //定义最小索引与数组每一项元素变量
    var minIndex,ele;
    for(var i = 0;i < len - 1;i++){
            //最小索引等于当前i值，相当于初始化值
            minIndex = i;
            //初始化每一项
            ele= arr[i];
         for(var j = 1;j < len;j++){
                //获取相邻数，比较大小，得到最小数索引
                if(arr[j] < arr[minIndex]){
                        minIndex = j;
                }
         }
         //将得到的最小数排列在最前面
        arr[i] = arr[minIndex];
        //与最小数做比较的值放在最小数所处的位置
        arr[minIndex] = ele;
    }
    return arr;
}
//测试:
selectSort(arr);//[25,35,50,55,60]

下面我们来测试一下代码运行时间。对每个元素进行查找时，意味着每个元素都要查找一次，所以运行时间为O(n),需要找出最小元素，又要检查每个元素，这意味着又要O(n)的运行时间。因此需要的总时间为O(nxn)=O(n^2)。这也就是说，需要执行n次操作。

选择排序只是一种很灵巧的算法，但还称不上速度最快，速度最快的是快速排序法。