有一本像小说一样有趣的算法入门书，我不会告诉你，它的封面是下面那样。
《图解算法》读后
一.二分查找
在大学毕业之际，室友聚餐，在等菜的时候，为了打发无聊的时间，大家又不想各看手机，最后决定玩猜数字游戏。每个人轮流各出一个数字，然后大家猜，在一百以内，
《图解算法》读后
大家没有从1开始去一个一个往上猜(不过这样的确可以打发时间)，大家都是从中间50开始猜的。
《图解算法》读后
不管是小了还是大了，首先会排除一半的数字，假设猜小了，那下一个人就会猜50到100中间的数字75，
《图解算法》读后
大了，那又排除了一半的数字，接下来的人就去猜50到75之间的数字63。
《图解算法》读后
是的，没错，这就是二分查找，每次猜测排除的数字个数如下，
《图解算法》读后
不管这个数字是多少，轮流到第7个人的时候一定会猜到。
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n(这里的2是底)步，而简单查找(前面所说的从1开始一个一个猜的情况)最多需要n步。
下面看看用python写的完整代码(书中的)：
《图解算法》读后
我用c语言给大家也给出了一个接口：
int SearchFun(int a[], int n, int x)
{
int mid,low,high;
low=0;
high=n-1;
while(low <= high)
{
mid=(low+high)/2;
if(a[mid] ==x)
return mid;
else if(a[mid] >x)
high = mid-1;
else
low = mid+1;
}
return -1;
}
运行时间
每次介绍算法时，我都将讨论其运行时间。一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。
回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。下表总结了我们发现的情况。
《图解算法》读后
常见的大O运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
❑ O(log n)，也叫对数时间，这样的算法包括二分查找。
❑ O(n)，也叫线性时间，这样的算法包括简单查找。
❑ O(n ＊ log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
❑ O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
❑ O(n! )，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
二、排序算法
二分查找法的前提是，查找的这一系列数字串必须是有序的。
在学习查找算法前我们简单的了解一下数组和链表。
数组链表
假设你要编写一个
管理待办事项的应用程序，为此你需要将这些待办事项储存在内存中，是使用数组还是链表呢？
我们先说使用数组吧，使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。
《图解算法》读后
如果你要添加第四个待办事项，但是第四个被别人给占了
《图解算法》读后
就相当于你和朋友一起去看电影，你们先左下，如果再来一个朋友，发现坐的地方没有空位置了，但你们必须要坐到一起，因此你们都要起来去找一个可以左下你们且椅子连着的位置。一个解决的办法是"预留座位"，即使只有三个人，但预留十个座位，这样一来，如果后面还有人来就不用再去占位置了，就相当于在图书馆里占座位，不过这样一来有两个缺点
1.浪费内存
2.如果超过了10个还得移位子
链表
链表中的元素可存储在内存的任何地方。
《图解算法》读后
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
《图解算法》读后
使用链表试，根本不需要移动元素。假设你与五位朋友去看一部很火的电影。你们六人想坐在一起，但看电影的人较多，没有六个在一起的座位。这个时候不需要坐在一起，链表相当于来说，"我们分开坐"，这也就是链表的优势——插入。
数组
链表在读取最后一个元素的时候，你不能直接去读取，因为你不知道它所处的地址，必须一个一个访问，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。
数组与此不同:你知道其中每个元素的地址。例如，假设有一个数组，它包含五个元素，起始地址为00，那么元素#5的地址是多少呢？
《图解算法》读后
只需执行简单的数学运算就知道：04。需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。
总结
链表的优势：插入、删除
数组的优势：读取
下面是常见数组和链表操作的运行时间。
《图解算法》读后
选择排序
看看书中的讲解。
你的计算机中储存了很多歌曲
《图解算法》读后
你要将这个列表按照从多到少的顺序排序，一种办法是我们遍历整个数组，找到听的次数最多的那首歌曲放到一个新列表中
《图解算法》读后
再次这样做，找到第二多
《图解算法》读后
继续这样做，你将得到一个这样的列表
《图解算法》读后
以上的排序方法就是选择排序，选择排序是一种灵巧的算法，但其速度不是很快。
python代码
《图解算法》读后
《图解算法》读后
我在此给出了c语言接口：
void SelectionSort(int *a,int len)
{
int i,j,k;
int temp;
for(i=0;i < len-1;i++)
{
k=i;
for(j=i+1;j<len;j++)
{
if(a[j] < a[k])
k=j;
}
if(k!=i)
{
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
注:文章中的图片均是来自本书。
网友评论