PHP 实现常用的四种算法排序

WechatIMG57.jpeg

冒泡排序

  • 介绍

从第一个数据开始,依次比较相邻元素的大小。如果前者大于后者,则进行交换操作,把大的元素往后交换。通过多轮迭代,直到没有交换操作为止。

  • 图解

冒泡排序.gif

  • 创建 bubble.php 内容如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
function bubble($arr){
$c = count($arr);
if ($c<=1) {
return $arr;
}
for ($i=0; $i < $c; $i++) {
for ($j=$i+1; $j < $c; $j++) {
if ($arr[$i]>$arr[$j]) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
return $arr;
}
var_dump(bubble([29,10,14,37,15]));
  • 执行
1
2
3
4
5
6
7
8
9
10
11
12
13
$ php bubble.php
array(5) {
[0] =>
int(10)
[1] =>
int(14)
[2] =>
int(15)
[3] =>
int(29)
[4] =>
int(37)
}

插入排序

  • 介绍

选取未排序的元素,插入到已排序区间的合适位置,直到未排序区间为空。

  • 图解

插入排序.gif

  • 创建 insert.php 内容如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?php
function insert($arr){
$c = count($arr);
if ($c<=1) {
return $arr;
}
for ($i=1; $i < $c; $i++) {
$temp = $arr[$i];
for ($j=$i-1; $j >= 0; $j--) {
if ($arr[$j]>$temp) {
$arr[$j+1] = $arr[$j];
}else{
break;
}
}
$arr[$j+1] = $temp;
}
return $arr;
}
var_dump(insert([29,10,14,37,15]));
  • 执行
1
2
3
4
5
6
7
8
9
10
11
12
13
$ php insert.php
array(5) {
[0] =>
int(10)
[1] =>
int(14)
[2] =>
int(15)
[3] =>
int(29)
[4] =>
int(37)
}

归并排序

  • 介绍

归并排序的原理其实就是分治法(二分法)。它采用了二分的迭代方式,首先将数组不断地二分,直到最后每个部分只包含 1 个数据。然后再对每个部分分别进行排序,最后将排序好的相邻的两部分合并在一起,这样整个数组就有序了。

  • 图解

归并排序.gif

  • 创建 merge.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
<?php 
function customMergeSort(&$arr, $start, $end){
if ($start < $end) {
$middle = floor(($start+$end)/2);
customMergeSort($arr, $start, $middle);
customMergeSort($arr, $middle+1, $end);
customDoubleMerge($arr, $start, $middle, $end);
}
}

function customDoubleMerge(&$arr, $start, $middle, $end){
$leftLen = $middle-$start+1;
$rightLen = $end-$middle;
$arrLeft = $arrRight = [];
for ($i=0; $i < $leftLen; $i++) {
$arrLeft[$i] = $arr[$start+$i];
}
for ($j=0; $j < $rightLen; $j++) {
$arrRight[$j] = $arr[$middle+$j+1];
}
$i = $j = 0;
$k = $start;
for (; $i < $leftLen && $j < $rightLen && $k < $end; $k++) {
if ($arrLeft[$i]<=$arrRight[$j]) {
$arr[$k] = $arrLeft[$i];
$i++;
} else {
$arr[$k] = $arrRight[$j];
$j++;
}

}
for (; $i < $leftLen && $k <= $end; $k++) {
$arr[$k] = $arrLeft[$i];
$i++;
}
for (; $j < $rightLen && $k <= $end; $k++) {
$arr[$k] = $arrRight[$j];
$j++;
}
}

$arr = [29,10,14,37,15];
$c = count($arr);
customMergeSort($arr, 0, $c-1);
var_dump($arr);
  • 执行
1
2
3
4
5
6
7
8
9
10
11
12
13
$ php merge.php
array(5) {
[0] =>
int(10)
[1] =>
int(14)
[2] =>
int(15)
[3] =>
int(29)
[4] =>
int(37)
}

快速排序

  • 介绍

快速排序法的原理也是分治法。它的每轮迭代,会选取数组中任意一个数据作为分区点,将小于它的元素放在它的左侧,大于它的放在它的右侧。再利用分治思想,继续分别对左右两侧进行同样的操作,直至每个区间缩小为 1,则完成排序。

  • 图解

快速排序.gif

  • 创建 quick.php 内容如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
function quick($arr){
$c = count($arr);
if ($c<2) {
return $arr;
}
$left = $right = [];
$middle = $arr[0];
for ($i=1; $i < $c; $i++) {
if ($arr[$i]<$middle) {
array_push($left,$arr[$i]);

}else{
array_push($right,$arr[$i]);
}
}
return array_merge(quick($left),[$middle],quick($right));
}
var_dump(quick([29,10,14,37,15]));
  • 执行
1
2
3
4
5
6
7
8
9
10
11
12
13
$ php quick.php
array(5) {
[0] =>
int(10)
[1] =>
int(14)
[2] =>
int(15)
[3] =>
int(29)
[4] =>
int(37)
}

选择排序

  • 介绍

每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

  • 图解

2022-11-03 10.19.45.gif

  • 创建 select.php 内容如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
function select($arr){
$c = count($arr);
if ($c < 2) {
return $c;
}
for ($i=0; $i < $c; $i++) {
$minKey = $i;
for ($j=$i+1; $j < $c; $j++) {
if ($arr[$j]<=$arr[$minKey]) {
$minKey = $j;
}
}
if ($minKey!=$i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minKey];
$arr[$minKey] = $temp;
}
}
return $arr;
}
var_dump(select([29,10,14,37,15]));
  • 执行
1
2
3
4
5
6
7
8
9
10
11
12
13
$ php select.php
array(5) {
[0] =>
int(10)
[1] =>
int(14)
[2] =>
int(15)
[3] =>
int(29)
[4] =>
int(37)
}

[[Go 实现常用的五种算法排序]]

-------------本文结束感谢您的阅读-------------
0%