自工作半年以来，或许前期把节奏崩的太紧了，最近半个月来很得空闲，PD无甚提需求，故而感到了深深的恐方（毛病啊~~），私心里想着得好好的充实一下自己。
研究生在校期间一直用C++语言，奈何天意弄人，工作后从事了PHP开发，虽然可以基本上手做些东西，但始终觉得有些根基发虚，不甚踏实。坦白而言，个人是不介意具体用哪种语言做开发的，私下认为只要问题理清，解决方法在，设计模式在，而具体用哪种语言来组织逻辑都不是重点。后来仔细想了想，似乎有点明白了为什么会觉得自己根基发虚：
1.虽然以前也用C++做过所谓的开发，但大多为科研项目，属小打小闹，算不上所谓的开发经验；C++语言相较于PHP的弱类型语言，是稍偏底层，感觉自己C++的基础底子还是有的，但从事PHP后，C++中积累的知识点，比如数据结构（链表，队列，栈等），语法细节（内存空间分配与回收等），算法（排序，递归，贪心）等等并没有应用到实际开发中，归根结底还是因为知识点片面并未真正系统化地融会贯通，而作为开发人员应该积累除的“设计经验/模式”，我亦半分没有，更别提在实际中操练了；所拥有的即将失去，这是恐方的原因之一；
2.既然已从事到PHP方面，理应踏踏实实，深入专研：比如服务器性能，MYSQL优化，LINUX网络编程，网络协议等等都该有所理解，但一方面由于缺乏交流和导向性（个人性格问题），也并未在这个上面去扑腾；另一方面可能尚未在这方面激发出兴趣，未体会到其中大意，故而也没太想花心思去主动获取；正在面临的没有拥抱，这是恐方的原因之二；
综上所述，以前在需求跟得紧，繁忙的时候没有回头反思，如今细思极恐，因空无一物，感到恐慌也实属正常。如若想不方，倒也容易，一句话：充实自己！由于在Web开发上还感到一头雾水，这个也可以慢慢来，个人觉得第一步是还要抓住即将失去的，故而开始在花了半日回忆C++基础语法细节后，我打算同时用PHP和C++语言把以前的基础再过一遍，就以经典的《算法导论》为素材吧。
另一方面，设计模式虽然以前有所了解，但现在最好也用PHP和C++再过一遍，书读百遍，其意自现嘛~~这两件事情同步做完后，乃是功法第一步，希望后面别忘了“拥抱变化”~~~
好了，废话少说，言归正传，《算法导论》第二章 算法入门，接招吧~~
2.1 插入排序
该排序算法见名知意（话说看名字第一眼，我是已经忘记了的，但花了几分钟，就想起了算法原理并给予实现），原理：数组是部分有序（前半部分）的，然后将无序的部分（待排序部分）循环插入到已有序的序列中。
//Insertion_sort
//C++实现
void insertion_sort(int *arr,int n){
for(int j=1;j<n;j++){
int key=arr[j];
int i=j-1;
while(i>=0&&arr[i]>val){
swap(arr[i],arr[i+1]);
i=i-1;
}
arr[i+1]=key;
}
}
//PHP实现
function insertion_sort(&$arr=array()){
if(count($arr)<2)
return;
for($j=1;$j<count($arr);j++){
$key=$arr[$j];
$i=$j-1;
while($i>=0&&$arr[$i]>$key) {
$arr[$i]=$arr[$i]+$arr[$i+1];
$arr[$i+1]=$arr[$i]-$arr[$i+1];
$arr[$i]=$arr[$i]-$arr[$i+1];
$i-=1;
}
$arr[i+1]=$key;
}
}
直接插入排序的性能分析：时间性能：平均情况、最坏情况下O（n*n）,最好情况下O(n)；空间性能O（1）；稳定排序。
2.2 分治排序
分治法：分解（Divide）：将原问题划分为n个规模较小而结构与原问题相似的子问题；解决(Conquer):递归的解决这些自问题，合并(Combine):然后再合并其结果，就得到原问题的解(这部分一般是分治算法核心)。
PHP实现：
function mergeSort(&$array,$cmp_function='strcmp'){
if(count($array)<2)
return;
//split the array in half recursively
$mid=count($array)/2;
$arr1=array_slice($array, 0,$mid);
$arr2=array_slice($array, $mid);
mergeSort($arr1,$cmp_function);
mergeSort($arr2,$cmp_function);
//conque and combine
//just all in order
if(call_user_func($cmp_function, end($arr1),$arr2[0])==1){
$array=array_merge($arr1,$arr2);
return;
}
//combine to ordered array
$array=array();
$pt1=$pt2=0;
while($pt1<count($arr1)&&$pt2<count($arrr2)){
if(call_user_func($cmp_function,$arr1[$pt1],$arr2[$pt2])==1){
$array[]=$arr1[$pt1++];
}else{
$array[]=$arr2[$pt2++];
}
}
while($pt1<count($arr1)){
$array[]=$arr1[$pt1++];
}
while($pt2<count($arr2)){
$array[]=$arr2[$pt2++];
}
return;
}
归并排序时间性能分析：算法最好、最坏、平均情况下的时间性能均为O(nlgn)，空间复杂度：O(n),稳定排序。
分治算法的运行时间可用一个递归方程式表示，该方程描述了子问题与原问题的关系，递归式如下：
根据a,b,以及D(n)+C(n)~O(n的d次方)，主定理如下：
注解：绝大多数情况下a=b；a<b的情况比如二分查找；a>b的情况，某些情况下子问题需多次利用或处理（Streen矩阵），所以a,b并不是随意的。
网友评论