分类灵魂思想下的文章

算法三：快速排序

作者: lane
时间: 2014-10-29
分类: 灵魂思想
1 条评论

快速排序，是最常用的排序算法，就是选择待排序的列表中的其中一个数字，作为基准数，然后把小于基准数的所有数字放到这个数的左边，大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分，左边和右边。第一部分，在左边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。第二部分，在右边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。ok，很明显，递归！

快速排序的时间复杂度在最坏的情况下是O(N2)，因为和冒泡排序一样，需要两两交换。平均情况下，快速排序的时间复杂度是O(NlogN)。

下面是C语言的代码

#include <stdio.h>

void quickSort(int left, int right, int *rank);

int main(){

int i, j, num, score, tmp;

printf("How many?\n");

scanf("%d", &num);

int rank[num];

for(i=0; i<num; i++){

printf("Enter Score:\n");

scanf("%d", &score);

//我们的试卷是0-100分的哦

if(score<0 || score > 100){

printf("Error");

return 1;

}

rank[i] = score;

}

printf("Rank:\n");

quickSort(0, num-1, rank);

for(i=0; i<num; i++){

printf("%d,", rank[i]);

}

return 0;

}

void quickSort(int left, int right, int *rank){

if(left > right){

return;

}

int i, j, t, tmp;

i = left;

j = right;

t = rank[left];

while(i!=j){

while(rank[j]>=t && i<j)

j--;

while(rank[i]<=t && i<j)

i++;

if(i < j){

tmp = rank[j];

rank[j] = rank[i];

rank[i] = tmp;

}

rank[left] = rank[i];

rank[i] = t;

quickSort(left, i-1, rank);

quickSort(i+1, right, rank);

}

算法二：冒泡排序

作者: lane
时间: 2014-10-28
分类: 灵魂思想
评论

冒泡排序是最被人熟知的排序算法。什么是冒泡排序？冒泡排序的特点是好邻居好说话，核心思想是一个每次比较两个相邻的元素，如果他们的大小顺序反了，就把他们交换过来。N个数就有N-1轮，每一轮把一个数字放在它正确的位置上。冒泡排序时间复杂度是O(N2)。C语言代码如下：

#include <stdio.h>

int main(){

int i, j, num, score, tmp;

printf("How many?\n");

scanf("%d", &num);

int rank[num];

for(i=0; i<num; i++){

printf("Enter Score:\n");

scanf("%d", &score);

//我们的试卷是0-100分的哦

if(score<0 || score > 100){

printf("Error");

return 1;

}

rank[i] = score;

}

printf("Rank:\n");

//冒泡排序

for(i=0; i<num-1; i++){

for(j=0; j<num-i; j++){

if(rank[j] > rank[j+1]){

tmp = rank[j];

rank[j] = rank[j+1];

rank[j+1] = tmp;

}

for(i=0; i<num; i++){

printf("%d,", rank[i]);

}

return 0;

}

算法一：桶排序

作者: lane
时间: 2014-10-27
分类: 灵魂思想
评论

桶排序，是最快最简单的排序。有多宽维度，就要申请多大的数组。比如100分的试卷，就要申请101个数组（试卷是0-100分），有人考了100分，就把array[100]加1，有人考了90，就把array[90]加1，有人考了70，就把array[70]+1，又有人考了90，就把array[90]加1，那么从高到底打印，如果是某个分数是0个人，就不打印，如果某个分数是1个人，就打印一次，如果某个分数是2个人，就打印两次，上面的例子就是100，90，90，90，70。

桶排序快是毋庸置疑的，但是，浪费了空间。比如打游戏，新手村里的小鸡攻击力是1，而最后一个副本的大BOSS的攻击力是999999999，那么就要对这个游戏的所有玩家和怪物的攻击力排序，就要申请一个1000000000长度的数组，就是array[1000000000]。假如每个字段的值都是1，1是整形，需要是4-8个字节（到底是4还是8取决于机器），那么这个数组就是1000000000/8/1024/1024=119MB。嗯哼？一个数组就要119M，你就是13年淘宝双11的160G内存的机器也拖不起吧。

桶排序的时间复杂度是O(M+N)，是最快的排序，它也是最简单的排序。

C语言代码：

#include <stdio.h>

int main(){

int i, j, num, score, rank[100];

for(i=0; i<101; i++){

rank[i] = 0;

}

//需要录入多少个数据

printf("How many?\n");

scanf("%d", &num);

for(i=0; i<num; i++){

printf("Enter Score:\n");

scanf("%d", &score);

//我们的试卷是0-100分的哦

if(score<0 || score > 100){

printf("Error");

return 1;

}

//进桶

rank[score]++;

score = 0;

}

printf("Rank:\n");

//打印

for(i=0; i<101; i++){

for(j=0; j<rank[i]; j++){

printf("%d,", i);

}

面向对象的洗礼：设计模式（二十八）之访问者模式

作者: lane
时间: 2014-05-04
分类: 灵魂思想
评论

访问者模式，是设计模式中最难的一种模式。访问者模式适用于数据结构相对稳定的系统。访问者模式对数据结构和作用于结构上的操作之间进行了一次解耦合。访问者模式的目的是把处理从数据结构分离出来。
访问者模式的适用场景：所开发的系统具有比较问题的数据结构，又有抑郁变化的算法。因为访问者模式使得算法操作的增加和扩展变得容易。优点是增加新的操作更加容易，因为增加新操作就是意味着增加新的访问者，访问者模式将有关的行为集中到一个对象中。缺点显而易见了，就是改变数据结构变得下个对困难。
访问者模式：表示一个作用于某对象的结构中的各个元素的操作。它使你可以在不改变各元素的前提下定义作用于这些元素的新操作。
场景：人类分为男女，对于人类这个系统，分类是非常固定的，一个元素是男，一个元素是女（人妖滚粗）。男女对同一件事情往往有不同的观点。以PHP为代码环境，模拟设计模式之访问者模式的代码实现。（暂时没有想到好的例子，就从《大话设计模式》中访问者模式摘了一段）

<?php
class Action{
    public function getManView(Man $manObj){}
    public function getWomanView(Woman $manObj){}
}
class Person{
    public function accept(Action $actionObj){}
}
class Success extends Action{
    public function getManView(Man $manObj){
        echo sprintf('%s成功时，背后多半有一个伟大的女人<br>', $manObj->getName());
    }
    public function getWomanView(Woman $womanObj){
        echo sprintf('%s成功时，背后多半有一个不成功的女人<br>', $womanObj->getName());
    }
}
class Failing extends Action{
    public function getManView(Man $manObj){
        echo sprintf('%s失败时，闷头喝酒，谁也不用劝<br>', $manObj->getName());
    }
    public function getWomanView(Woman $womanObj){
        echo sprintf('%s失败时，眼泪汪汪，谁也劝不住<br>', $womanObj->getName());
    }
}
class Love extends Action{
    public function getManView(Man $manObj){
        echo sprintf('%s恋爱时，凡事不懂也要装懂<br>', $manObj->getName());
    }
    public function getWomanView(Woman $womanObj){
        echo sprintf('%s恋爱时，凡事懂也要装不懂<br>', $womanObj->getName());
    }
}
class Man extends Person{
    private $name = '男人';
    public function getName(){
        return $this->name;
    }
    public function accept(Action $actionObj){
        $actionObj->getManView($this);
    }
}
class Woman extends Person{
    private $name = '女人';
    public function getName(){
        return $this->name;
    }
    public function accept(Action $actionObj){
        $actionObj->getWomanView($this);
    }
}
class ObjectStructure{
    private $elementList;
    public function add(Person $elementObj){
        $this->elementList[] = $elementObj;
    }
    public function display(Action $visitorObj){
        foreach($this->elementList as $element){
            $element->accept($visitorObj);
        }
    }
}
//客户端/接口
$o = new ObjectStructure();
$o->add(new Man());
$o->add(new Woman());

$successObj = new Success();
$o->display($successObj);

$failingObj = new Failing();
$o->display($failingObj);

$loveObj = new Love();
$o->display($loveObj);

这里用到一个双分派技术。客户端将状态（成功、失败、恋爱）作为参数传递给男人，这是第一次分派。男人类调用作为参数的“具体状态中的方法-男人的观点”，同时将自身传递给状态的对象，这是第二次分派。双分派意味着得到执行的操作决定于请求的种类和两个接收者的类型。双分派的好处是，如果要增加结婚类，只需要增加如下：

class Marry extends Action{
    public function getManView(Man $manObj){
        echo sprintf('%s结婚时，有妻徒刑<br>', $manObj->getName());
    }
    public function getWomanView(Woman $womanObj){
        echo sprintf('%s结婚时，婚姻保险<br>', $womanObj->getName());
    }
}

除此之外，客户端在需要的时候调用即可。不需要动其他的代码，增加新算法，只需要扩展一个新类。完美体现开放-封闭原则。

面向对象的洗礼：设计模式（二十七）之解释器模式

作者: lane
时间: 2014-05-03
分类: 灵魂思想
评论

解释器模式，作为PHPer应该非常非常非常熟悉的一种，尽管不知道它叫做解释器模式，但是肯定使用过它。在解释器模式的最佳应用，就是大量优秀的模板引擎。解释器模式解决了一种特定的类型的问题发生的频率足够高，那么就可能值得将该问题的各个势力表述为一个简单的语言中的句子。这就构建了一个解释器，解释器他哦各国解释这些句子来解决问题。
解释器模式：给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。
比如：模板引擎smart；比如论坛的UBB代码，就是用[url=http://www.lanecn.com]LaneBlog[/url]来表示<a href="http://www.lanecn.com/>LaneBlog</a>；还比如正则表达式等
场景：a表示你，b表示好，c表示世界。1表示我说，2表示你说。以PHP为代码环境，模拟设计模式之解释器模式的代码实现。

<?php
class Content{
    private $content = '';
    public function get(){
        return $this->content;
    }
    public function set($content){
        $this->content = $content;
    }
}
class Expression{
    public function interpret($contentObj){
        $content = $contentObj->get();
        if(!empty($content)){
            $lenth = strlen($content);
            for($i=0; $i<$lenth; $i++){
                if(is_numeric($content[$i])){
                    Number::excute($content[$i]);
                }else if(is_string($content[$i])){
                    String::excute($content[$i]);
                }
            }
        }
    }
}
class Number{
    public static function excute($value){
        $data = '';
        switch($value){
            case 1:
                $data = '我说：';
                break;
            case 2:
                $data = '你说：';
                break;
            default:
                break;
        }
        echo $data;
    }
}
//a表示你，b表示好，c表示世界。1表示我说，2表示你说
class String{
    public static function excute($value){
        $data = '';
        switch($value){
            case 'a':
                $data = '你';
                break;
            case 'b':
                $data = '好';
                break;
            case 'c':
                $data = '世界';
                break;
            default:
                break;
        }
        echo $data;
    }
}
//客户端/接口
$contentObj = new Content();
$str = '1abc';
$contentObj->set($str);
echo '解密' . $str . '：<br>';
$expression = new Expression();
$expression->interpret($contentObj);
echo '<br>';
$str = '2abc';
$contentObj->set($str);
echo '解密' . $str . '：<br>';
$expression = new Expression();
$expression->interpret($contentObj);