新浪PHP开发工程师笔/面试总结八·PHP实现快速排序和归并排序

不出意外应该是最后一篇了…接下来的日子要安心弄一门语言了

用PHP实现快排和归并排序花了我一个晚上加一个白天的时间…总结这篇估计也要2个小时…

1、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function qsort($seq) {
$count = count($seq);
if( $count > 1 ) {
$pivot = $seq[0];
$less = array();
$greater = array();
for ($i = 1; $i < $count; $i++) {
if ($seq[$i]<=$pivot) {
$less[] = $seq[$i];
} else {
$greater[] = $seq[$i];
}
}
$less = qsort( $less );
$greater = qsort( $greater );
return array_merge($less,array($pivot),$greater);
} else {
return $seq;
}
}

这个是快速排序的简单版本,和维基百科上的完全一样,不过上述程序一度无法运行,一直提示内存耗尽…

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 40 bytes)

后来检查了代码,发现错在对基准数pivot的处理上,一开始我为了想标新立异,想弄个和维基不一样的解法。

原来的想法大概是:pivot放在less那边,然后merge的时候就只需要merge(less,greater)就可以了…

后来发现这样做的话,less子数组就永远≥2了,所以分片操作会一直进行直到内存耗尽…所以和维基上的相比也就没有改进了…

之后是快排的in-place版:

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
function quicksort(&$seq,$left,$right){
if($right>$left){
$pivot_index = $left;
$new_pivot_index = partition($seq,$left,$right,$pivot_index);
quicksort($seq,$left,$new_pivot_index-1);
quicksort($seq,$new_pivot_index+1,$right);
}
}
function partition(&$seq,$left,$right,$pivot_index){
swap($seq[$pivot_index],$seq[$right]);
$store_index = $left;
for($i=$left;$i<$right;$i++){
if($seq[$i]<=$seq[$right]){
swap($seq[$store_index],$seq[$i]);
$store_index++;
}
}
swap($seq[$store_index],$seq[$right]);
return $store_index;
}
function swap(&$one,&$two){
$temp = $two;
$two = $one;
$one = $temp;
}
function entry(&$seq){
quicksort($seq,0,count($seq)-1);
}

原地分区(in-place)版的好处是不需要额外的存储空间,但是理解起来还是花了一些时间。

以上代码由三个主要函数组成,quicksort()函数负责控制迭代过程;partition()函数负责分区,在分区的过程中实现排序;最后是swap()函数负责交换元素的次序。

需要理解的地方就是分区函数partition()的实现,store_index这个“指针”是分区的依据,通过store_index指针,把比基准数小的数全部换到前面(“左边”区域),然后把基准数交换到左边区域的右边一个元素。以这种方式让左区都小于基准,右区都大于基准。在实现in-place版时,我就是对着伪代码写的,所以一次就成功了。

维基百科上还说,随机选择基准数的索引index可以让运算更有效率…感觉不是很难,就没实现…

2、归并排序

归并排序在维基上的词条里没有伪代码和php实现,最接近的C++实现也好长…只好自己闷头“理解了一会”。最后得出的结论大概也是不停地分子数组,直到每个数组的元素都只有一个,然后进入归并的进程,代码实现如下:

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
function merge_sort($seq){
$size = count($seq);
if($size>1){
$mid_count = floor($size/2);
$sub_left = merge_sort(array_slice($seq,0,$mid_count));
$sub_right = merge_sort(array_slice($seq,$mid_count));
return merge($sub_left,$sub_right);
} else {
return $seq;
}
}

function merge($sub_left,$sub_right){
$result = array();
while(!empty($sub_left)&&!empty($sub_right)){
if($sub_left[0]<$sub_right[0]){
array_push($result,array_shift($sub_left));
} else {
array_push($result,array_shift($sub_right));
}
}
while(!empty($sub_left))
array_push($result,array_shift($sub_left));
while(!empty($sub_right))
array_push($result,array_shift($sub_right));
return $result;
}

为了实现上述算法,我还看了一下array_push()array_shift()array_slice()三元运算符的用法…因为感觉上面的代码太长了,想用三元运算符压缩一下:

array_push($arr_c,array_shift($arr_one[0]<$arr_two[0]?$arr_one:$arr_two));

其实最后执行起来和用if应该没什么速度上的差别…不过就是看起来比较爽,不料竟然跑不动…会提示以下内容:

Fatal error: Only variables can be passed by reference in /var/www/shift.php on line 5

在array_shift函数的文档下有人发了如下解释:

I haven’t really read into it, but if you’re complaining about a change in PHP 5.0.5 that made it so you couldn’t do: $val = array_shift(preg_split()); or $val = array_shit(function_that_returns_array); Then you’re not using this function correctly. This function’s argument is supposed to be a pointer to a variable. It then modifies that variable and returns a value. When you specify a function, php CAN NOT modify the return value of that function. It should be common sense but apparently its not.

大意是array_shift函数应该传入一个数组的指针,因为这个函数不能对另一个函数返回的数组(函数的返回值)进行操作。

后来就用if实现了…不过通过调试这个bug,我也知道了三元选择符的用法,还专门验证了分片函数是否可用,也算积累了一点经验吧!

3、写在最后的话:

这个面经完成历时一个月…中间穿插了各种毕业活动以及搬行李回家等等过程,能够写完真是可喜可贺。通过这次面试,我最切身的体会就是想要学好一门语言,务必要把这些基本的内容都自己敲一遍跑一跑,最好自己想改进一下,然后弄出点bug,然后对很多功能就可以理解得更深了。

所以,我还没有上路呢…接下来的时间要好好努力了!