算法面试题集1

Published: 16 Oct 2015 Category: algorithm

参考:算法速成系列(7th day)

1、希尔排序

观察一下”插入排序“:其实不难发现她有个缺点:

如果当数据是”5, 4, 3, 2, 1“的时候,此时我们将“无序块”中的记录插入到“有序块”时,每次插入都要移动位置,此时插入排序的效率可想而知。

shell根据这个弱点进行了算法改进,融入了一种叫做“缩小增量排序法”的思想,其实也蛮简单的,不过有点注意的就是: 增量不是乱取,而是有规律可循的。

"shellSort"
第一次增量的取法为: d=count/2;

第二次增量的取法为: d=(count/2)/2;

最后一直到: d=1;

2、hash查找

O(1)的查找时间。

做哈希必须要遵守两点原则:

①:key尽可能的分散,也就是我丢一个“6”和“5”给你,你都返回一个“2”,那么这样的哈希函数不尽完美。

②:哈希函数尽可能的简单,也就是说丢一个“6”给你,你哈希函数要搞1小时才能给我,这样也是不好的。

2.1 常用的做哈希的手法有“五种”:

第一种:”直接定址法“。 很容易理解,key=Value+C; 这个“C”是常量。Value+C其实就是一个简单的哈希函数。

第二种:“除法取余法”。 很容易理解, key=value%C;解释同上。

第三种:“数字分析法”。 这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033, 针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是 key1=22,key2=26,key3=90。

第四种:“平方取中法”。此处忽略,见名识意。

第五种:“折叠法”。 这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160, 然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相关,来做到“散列地址”尽可能分散的目地。

2.2 解决冲突常用的手法也就2种:

第一种: “开放地址法“。 所谓”开放地址“,其实就是数组中未使用的地址。也就是说,在发生冲突的地方,后到的那个元素(可采用两种方式 :①线性探测,②函数探测)向数组后寻找”开放地址“然后把自己插进入。

第二种:”链接法“。 这个大家暂时不懂也没关系,我就先介绍一下原理,就是在每个元素上放一个”指针域“,在发生冲突的地方,后到的那个元素将自己的数据域抛给冲突中的元素,此时冲突的地方就形成了一个链表。

其他查找方法

顺序查找、二分查找、哈希查找