PHP算法学习笔记

12月 2, 2015

桶排序

申请同样大小的数组,遇见键值等于数值就数值就加1,然后数值是有多少就打印多少个键值,复杂度O(M+N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
$input = [5, 3, 5, 2, 8]; //待排序数组

/*申请空间*/
for ($i = 0; $i <= 10; $i++) {
$arr[] = 0;
}

$count = count($input); //记录数组的大小

/*桶排序*/
for ($i = 0; $i < $count; $i++) {
$j = $input[$i]; //将每一个数记录到$j中
$arr[$j]++; //计数
}


/*输出*/
for ($i = 10; $i >= 0; $i--) {
for ($j = 1; $j <= $arr[$i]; $j++) {
echo "$i\n";
}
}

冒泡排序

两两对比,位置错误就交换顺序,复杂度O(N²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<?php
$input = [12, 35, 99, 18, 76];
$count = count($input);
for ($i = 0; $i <= $count; $i++) { //外循环次数
for ($j = 0; $j < $count - $i - 1; $j++) { //内循环少一次
$z = $j + 1; //往后一位对比,这就是内循环少一次的原因
if ($input[$j] < $input[$z]) { //前面一位小于后一位,则调换顺序
$t = $input[$j];
$input[$j] = $input[$z];
$input[$z] = $t;
}
}
}
var_dump($input);

快速排序

选择一个基准元素,通常选择第一个元素或者最后一个元素。扫描一趟,将待排序列分成两部分,一部分小于基准元素小,一部分大于等于基准元素。此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

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
var $input = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8, 9];

public function run()
{
$n = count($this->input);
$this->quickSort(0, $n - 1);
}

public function quickSort($left, $right)
{
if ($left > $right) {
return;
}
$i = $left;
$j = $right;

$target = $this->input[$left];
while ($i != $j) {
//右指针开始
if ($this->input[$j] >= $target && $i < $j) {
$j--;
}

if ($this->input[$i] <= $target && $i < $j) {
$i++;
}

//交换位置
if ($i < $j) {
$temp = $this->input[$i];
$this->input[$i] = $this->input[$j];
$this->input[$j] = $temp;
}
}

//将判断的基数放到中间归为
$this->input[$left] = $this->input[$i];
$this->input[$i] = $target;

$this->quickSort($left, $i - 1);
$this->quickSort($i + 1, $right);

return;
}

归并排序

归并排序:就是利用归并(合并)的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列;再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序。

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
public function run()
{
$array = [34, 5, 555, 14, 88, 5];
$this->mergeSort($array, 0, count($array) - 1);
var_dump($array);
}

public function mergeSort(array &$array, $left, $right)
{
if ($left < $right) {
$mid = ($left + $right) >> 1;
$this->mergeSort($array, $left, $mid);
$this->mergeSort($array, $mid + 1, $right);
$this->merge($array, $left, $mid, $right);
}
}

public function merge(array &$array, $left, $mid, $right)
{
$i = $left;
$j = $mid + 1;
$k = $left;
$temp = [];

while ($i != $mid + 1 && $j != $right + 1) {
if ($array[$i] >= $array[$j]) {
$temp[$k++] = $array[$j++];
} else {
$temp[$k++] = $array[$i++];
}
}

//将左边的剩余部分添加到temp数组中
while ($i != $mid + 1) {
$temp[$k++] = $array[$i++];
}

//将右边的剩余部分添加到temp数组中
while ($j != $right + 1) {
$temp[$k++] = $array[$j++];
}

//将临时数组覆盖到array
for ($i = $left; $i <= $right; $i++) {
$array[$i] = $temp[$i];
}
}

二分查找算法

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
public function run()
{
$array = [0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99];
$result = $this->binarySearch($array, 99);
var_dump($result);
}

public function binarySearch($array, $target)
{
$length = count($array);
$low = 0;
$high = $length - 1;

while ($low <= $high) {
$mid = ($high + $low) >> 1;
if ($target < $array[$mid]) {
$high = $mid - 1;
} elseif ($target > $array[$mid]) {
$low = $mid + 1;
} else {
return $mid;
}
}

return false;
}