作者归档：admin

PHP源码阅读笔记二十六：PHP快速排序源码实现的简化版本

PHP源码阅读笔记：PHP中的快速排序实现的简化版本
这段时间在复习数据结构，有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式，在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到，也许是为了兼容多种数据类型，所以其在交换及比较位置比较复杂，看起来也比较纠结，于是自己将
其中的类型全部换成int类型，得到简化版本的PHP源码中的快速排序
其代码如下 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <stdio.h>
 
static qsort_swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
 
void qsort(int *base, int nmemb)
{
	int *begin_stack[10];
	int *end_stack[10];
	int *begin;
	int *end;
	int *seg1;
	int *seg2;
	int *seg2p;
	int loop;
	unsigned int offset;
 
	/* 使用栈而不是常见的递归实现 */
	begin_stack[0] = base;	//	开始元素位置栈，入栈
	end_stack[0]   = base + (nmemb - 1) ;	//	结束位置栈，入栈
 
	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];	//	开始位置出栈
		end   = end_stack[loop];	//	结束位置出栈
 
		while (begin < end) {
			offset = (end - begin) >> 1;	//	取中间位置
 
			qsort_swap(begin, begin + offset);	//	交换开始和中间的位置
 
			seg1 = begin;
			seg2 = end;
 
			while (1) {
				for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1);
 
				for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1);
 
				if (seg1 >= seg2)
					break;
 
				qsort_swap(seg1, seg2);
			}
 
			qsort_swap(begin, seg2);
 
			seg2p = seg2;
 
			if ((seg2p - begin) <= (end - seg2p)) {
				if (seg2p < end) {	//	右侧入栈
					begin_stack[loop] = seg2p + 1;
					end_stack[loop++] = end;
				}
				end = seg2p;
			} else {
				if (seg2p > begin) {	// 左侧入栈
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - 1;
				}	//	end if
				begin = seg2p;
			}	//	end if
		}	//	end while
	}	//	end for
 
}
int main(int argc, char *argv[])
{
	int a[10] = {14, 5, 7, 8, 2, 4, 55, 3};
	int i;
	qsort(a, 8);
	for (i = 0; i < 8;i++) 
	{
		printf("%d ", a[i]);
	}
	return 0;
}

看完后，有一个感受：强大的指针，受益非浅！

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序
【基本概念】
排序：排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
内排序：内排序指的是待排序记录在放在计算机随机存储器中进行的排序过程
内排序大致可分为插入排序、交换排序、选择排序、归并排序和计数排序
在排序的过程中需要进行两种基本操作：1、比较两个关键字的大小，2、将记录从一个位置移动到另一个位置
【冒泡排序过程】
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较批二个记录和第三个记录的关键字，依次类推，直至第n-1个元素和第n个元素进行过比较为止。以上为一次冒泡排序，礤结果是使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二真趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录安置到第n-1人的位置上，如此类似
【冒泡排序的PHP实现】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

<?php
/**
 * 数据结构中冒泡排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                    
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 冒泡排序 将数组从小到排序
 * @param array $array 需要排序的数据
 * @return array
 */
function bubble_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(bubble_sort($array));
?>

【简单选择排序的过程】
选择排序的基本思想是：每一趟在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录
其中最简单的是简单选择排序，其过程如下：
通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并各第i个记录交换之。
【简单选择排序的PHP实现】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

<?php
/**
 * 数据结构中简单选择排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                 
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 简单选择排序，将数组从小到大排序
 * @param array $array 需要进行排序的数组
 * @return array $array
 */
function select_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(select_sort($array));
?>

温故知新，以前对这两种排序方式一直模糊不清，总算了结了

PHP设计模式笔记：使用PHP实现策略模式

PHP设计模式笔记：使用PHP实现策略模式

【意图】
定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换。策略模式可以使算法可独立于使用它的客户而变化
策略模式变化的是算法

【策略模式结构图】

策略模式

策略模式

【策略模式中主要角色】
抽象策略(Strategy）角色：定义所有支持的算法的公共接口。通常是以一个接口或抽象来实现。Context使用这个接口来调用其ConcreteStrategy定义的算法
具体策略(ConcreteStrategy)角色：以Strategy接口实现某具体算法
环境(Context)角色：持有一个Strategy类的引用，用一个ConcreteStrategy对象来配置

【策略模式的优点和缺点】
策略模式的优点：
1、策略模式提供了管理相关的算法族的办法
2、策略模式提供了可以替换继承关系的办法 将算封闭在独立的Strategy类中使得你可以独立于其Context改变它
3、使用策略模式可以避免使用多重条件转移语句。

策略模式的缺点：
1、客户必须了解所有的策略 这是策略模式一个潜在的缺点
2、Strategy和Context之间的通信开销
3、策略模式会造成很多的策略类

【策略模式适用场景】
1、许多相关的类仅仅是行为有异。“策略”提供了一种用多个行为中的一个行为来配置一个类的方法
2、需要使用一个算法的不同变体。
3、算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的，与算法相关的数据结构
4、一个类定义了多种行为，并且 这些行为在这个类的操作中以多个形式出现。将相关的条件分支移和它们各自的Strategy类中以代替这些条件语句

【策略模式与其它模式】
Template模式：模板方法模式与策略模式的不同在于，策略模式使用委派的方法提供不同的算法行为，而模板方法使用继承的方法提供不同的算法行为
享元模式(flyweight模式)：如果有多个客户端对象需要调用 同样的一睦策略类的话，就可以使它们实现享元模式

【策略模式PHP示例】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

 
<?php
/**
 * 策略模式的PHP简单实现 2010-07-25 sz
 * @author 胖子 phppan.p#gmail.com  http://www.phppan.com                                                  
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象策略角色，以接口实现
 */
interface Strategy {
 
    /**
     * 算法接口
     */
    public function algorithmInterface();
}
 
/**
 * 具体策略角色A
 */
class ConcreteStrategyA implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface A<br />';
    }
}
 
/**
 * 具体策略角色B
 */
class ConcreteStrategyB implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface B<br />';
    }
}
 
/**
 * 具体策略角色C
 */
class ConcreteStrategyC implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface C<br />';
    }
}
 
/**
 * 环境角色
 */
class Context {
    /* 引用的策略 */
    private $_strategy;
 
    public function __construct(Strategy $strategy) {
        $this->_strategy = $strategy;
    }
 
    public function contextInterface() {
        $this->_strategy->algorithmInterface();
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
    /**
     * Main program.
     */
    public static function main() {
        $strategyA = new ConcreteStrategyA();
        $context = new Context($strategyA);
        $context->contextInterface();
 
        $strategyB = new ConcreteStrategyB();
        $context = new Context($strategyB);
        $context->contextInterface();
 
        $strategyC = new ConcreteStrategyC();
        $context = new Context($strategyC);
        $context->contextInterface();
    }
 
}
 
Client::main();
?>