【好书共享】《算法图解》让算法变得有趣
阅读计划
Panda姐这个星期每天花了一个小时看这本书，到今天看到了第四章，总该对算法有点认知了。《算法图解》这本书比《算法》、《算法导论》看起来有趣易懂多了，里面读了写漫画式的算法解读。二分查找在我们生信技能树的编程实战中涉及到过，后面的贪婪算法、动态规划、K最邻算法在生信软件文章中都能时常能看到。下图中表明为掌握的内容，希望大家购入此书时重点学习。
Panda姐的学习笔记
第一章 算法简介
曾经实验室编程学习之风，盛极一时。常见大家用各自的语言进行编程来解决同一个需求，一般的情况下是
perl最快，Python次之，R最慢。除了语言导致问题解决时间多少，然后就是算法啦。在我的 【R】Project Euler通关打怪兽:http://shemy.site/2017/11/20/The-projecteuler-practice/ 文章中，很多时候我解决问题的方法并不是最好，绝大所数是能得到答案，运行时间相当的长。现在让我回过头去做的话，我会想着用哪种算法速度更快，找到更优的解决办法。
### 二分法
binary_search <- function(list,item){
low = 1
high = length(list)
while(low <= high){
mid = (low+high)/2
guess = list[mid]
if(guess == item){
return(mid)
}
if(guess >item){
high = mid
}else{
low = mid
}
}
return("none")
}
my_list <- c(1,3,5,7,9)
binary_search(my_list,7)
my_list[4]
# 练习
# 1.1 假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请问最多需要几步才能找到？
log2(128)
# 最多需要7步
# 1.2 上面列表的长度翻倍后，最多需要几步？
log2(128*2)
# 翻倍后，最多需要8步
第二章 选择排序
Panda姐写代码从来不考虑内存的问题，能把数据格式整理好就好了。反正不懂内存的工作原理，今天一看略懂略懂。
findSmallest <- function(arr){
smallest = arr[1]
smallest_index = 1
for (i in 1:length(arr)){
if(arr[i] < smallest){
smallest = arr[i]
smallest_index = i
}
}
return(smallest_index)
}
selectionSort <- function(arr){
newArr = c()
for(i in 1:length(arr)){
smallest = findSmallest(arr)
newArr[i] = arr[smallest]
arr = arr[-smallest]
}
return(newArr)
}
selectionSort(c(5,3,6,2,10))
第四章 快速排序.png
这章的快速排序函数，我竟然忘记怎么筛选向量了，看的书全还忘了，计划最近去重新翻翻以前看的R入门书啦~
#函数：quickSort()
#功能：快速排序
#思路：对向量(5,4,12,13,3,8)排序。首先将所有元素跟第一个元素5进行比较，
# 从而形成两个子向量：一个由小于5的元素组成(4,3)，一个由大于5元素组成(12,13,8)。
# 然后在子向量上递归调用quickSort()，返回(3,4),(8,12,13)，最后将两个子向量和5一起组合得到向量(3,4,5,8,12,13)
# 来源： https://blog.csdn.net/firparks/article/details/50562400
-------------------------------------------------------------------------------------------------------------
quickSort<-function(x)
{
if(length(x)<=1) return(x)
point<-x[1]
t<-x[-1]
sv1<-t[t<point]
sv2<-t[t>=point]
sv1<-quickSort(sv1)
sv2<-quickSort(sv2)
return(c(sv1,point,sv2))
}
quickSort(c(5,4,12,13,3,8))
#函数：quickSort()
#功能：快速排序
#思路：对向量(5,4,12,13,3,8)排序。首先将所有元素跟第一个元素5进行比较，
# 从而形成两个子向量：一个由小于5的元素组成(4,3)，一个由大于5元素组成(12,13,8)。
# 然后在子向量上递归调用quickSort()，返回(3,4),(8,12,13)，最后将两个子向量和5一起组合得到向量(3,4,5,8,12,13)
# 来源： https://blog.csdn.net/firparks/article/details/50562400
-------------------------------------------------------------------------------------------------------------
quickSort<-function(x)
{
if(length(x)<=1) return(x)
point<-x[1]
t<-x[-1]
sv1<-t[t<point]
sv2<-t[t>=point]
sv1<-quickSort(sv1)
sv2<-quickSort(sv2)
return(c(sv1,point,sv2))
}
quickSort(c(5,4,12,13,3,8))