PHP常用算法
基于选择的排序算法
常见的基于选择的排序算法有:冒泡排序、插入排序、选择排序、归并排序和快速排序,我们在选在排序算法的时候,通常会根据以下几个维度来考虑:
- 时间复杂度
- 空间复杂度(对内存空间的消耗)
- 算法的稳定性(如果待排序的序列中存在值相等的元素,经过排序之后,相同元素之间原有的先后顺序不变)
介绍一个网站https://visualgo.net/en/sorting。该网站以动图的形式展示了排序过程,对学习者来说,非常的友好直观。
1. 冒泡排序
- 实现原理:
冒泡排序每次只会操作相邻的两个元素,将其进行比较:大的放在后面,小的放在前面。经过一轮冒泡后,最大的值移动到最后的位置。
- 性能分析:
- 时间复杂度:O();
- 空间复杂度:只涉及相邻的两个元素的交换,是
原地排序算法
;- 算法稳定性:元素相等不会交换,是稳定的排序算法。
时间复杂度是O(n^2),性能并不算好,所以我们在实践中基本不会选用冒泡排序
- 示例代码
<?php
/**
* Created by PhpStorm.
* User: liufeng
* Date: 2019/12/4
* Time: 11:14
*/
class Rand
{
public $randData = [];
public function __construct($num)
{
for ($i = 0; $i < $num; $i++) {
$this->randData[] = rand(0, 100);
}
}
}
function bubble_sort(array $arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
for ($i = 0; $i < $len; $i++) {
$flag = false;
for ($j = 0; $j < $len - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];
$flag = true;
}
}
if (!$flag)
break;
}
return $arr;
}
$rand = new Rand(10);
$randData = $rand->randData;
echo '<pre>';
print_r($randData);
/************** 计算使用时间 ******************/
$start_time = microtime(true);
print_r(bubble_sort($randData));
$end_time = microtime(true);
echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';
2.插入算法
实现原理
将数组中的数据分成两个区间,已排序区间
和未排序区间
。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中的元素为空,排序结束。
性能分析
- 时间复杂度:O();
- 空间复杂度:没有额外的存储空间,是
原地排序算法
;- 算法稳定性:相同元素不会交换,是稳定的排序算法。
插入排序的时间复杂度和冒泡排序是一样的,也是不理想的,但是插入排序不涉及数据交换,从更细粒度来区分,性能略优于冒泡排序(核心代码中,冒泡需要三次赋值,而插入只需要一次赋值)
- 示例代码
<?php
/**
* Created by PhpStorm.
* User: liufeng
* Date: 2019/12/4
* Time: 11:14
*/
class Rand
{
public $randData = [];
public function __construct($num)
{
for ($i = 0; $i < $num; $i++) {
$this->randData[] = rand(0, 100);
}
}
}
function insert_sort(array $arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
for ($i = 1; $i < $len; $i++) {
$value = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
if ($arr[$j] > $value)
$arr[$j + 1] = $arr[$j];
else
break;
}
$arr[$j + 1] = $value;
}
return $arr;
}
$rand = new Rand(10);
$randData = $rand->randData;
echo '<pre>';
print_r($randData);
/************** 计算使用时间 ******************/
$start_time = microtime(true);
print_r(insert_sort($randData));
$end_time = microtime(true);
echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';
3. 选择排序
实现原理
选择排序算法的实现思路有点类似插入算法
,也分为已排序区间和未排序区间。但是选择排序每次都会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
性能分析
- 时间复杂度:O();
- 空间复杂度:不涉及额外的存储空间,所以是
原地排序算法
;- 算法稳定性:由于涉及到非相邻元素的位置交换,所以是不稳定的排序算法。
冒泡排序、插入排序、选择排序,时间复杂度都是一样的O(n^2),也都是原地排序,但是选择排序是不稳定的排序算法。另外,在插入排序中提到了冒泡和插入的区别。所以,综合比较下来,三者的优先级是:
插入排序 > 冒泡排序 > 选择排序。
- 示例代码
<?php
/**
* Created by PhpStorm.
* User: liufeng
* Date: 2019/12/4
* Time: 11:14
*/
class Rand
{
public $randData = [];
public function __construct($num)
{
for ($i = 0; $i < $num; $i++) {
$this->randData[] = rand(0, 100);
}
}
}
function select_sort(array $arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
for ($i = 0; $i < $len; $i++) {
$min = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] < $arr[$min]) {
$min = $j;
}
}
if ($min != $i) {
list($arr[$min], $arr[$i]) = [$arr[$i], $arr[$min]];
}
}
return $arr;
}
$rand = new Rand(10);
$randData = $rand->randData;
echo '<pre>';
print_r($randData);
/************** 计算使用时间 ******************/
$start_time = microtime(true);
print_r(select_sort($randData));
$end_time = microtime(true);
echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';
4. 归并算法
实现原理
所谓的归并算法,是指如果要排序一个数组,我们先把数组从中间分成前后两个部分,然后对前后两个部分分别进行排序,再将排好序的两个部分合并起来,这样整个数组就是有序的了。
归并算法使用了分治思想,使用递归的方法将一个数组一分为二,直到不能分割,然后将排序后序列合并,最终返回排序后的数组。
性能分析
- 时间复杂度:O(nlogn);
- 空间复杂度:归并算法需要额外的内存空间来存放数据,不是原地排序,最多需要和待排序数组同样大小的空间,所以空间复杂度是O(n);
- 算法稳定性: 不涉及相同元素位置交换,是稳定的排序算法。
归并排序O(nlogn)由于冒泡排序和插入排序O(n^2)
- 示例代码
<?php
/**
* Created by PhpStorm.
* User: liufeng
* Date: 2019/12/4
* Time: 12:18
*/
require_once './rand.php';
$rand = new Rand();
$originData = $rand->my_rand(10);
echo '<pre>';
print_r($originData);
function mergeSort(array $arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
$left = mergeSort(array_slice($arr, 0, floor($len / 2)));
$right = mergeSort(array_slice($arr, floor($len / 2)));
return merge($left, $right);
}
function merge(array $left, array $right)
{
$arr = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$arr[] = $left[$i];
$i++;
} else {
$arr[] = $right[$j];
$j++;
}
}
$arr = array_merge($arr, array_slice($left, $i));
$arr = array_merge($arr, array_slice($right, $j));
return $arr;
}
/************** 计算使用时间 ******************/
$start_time = microtime(true);
print_r(mergeSort($originData));
$end_time = microtime(true);
echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';
5. 快速排序
实现原理
在数组中选一个基准数(pivot),将基准数跟数组中的其他数进行比较,大于基准值的数放在右侧区间,小于基准值的数放在左区间,基准值放到中间。然后分治、递归处理,直至区间缩小为1,这时候所有数据都已排好序了。
性能分析
- 时间复杂度:O(nlogn),这个时间复杂度数据量越大,越优于O();
- 空间复杂度:不需要额外的存储空间,是原地排序;
- 算法稳定性:涉及到数据的交换,有可能破坏原来相同元素的位置排序,所以是不稳定的排序法。
常规排序中综合排名最高的排序算法,称为"快排";快排不需要像归并那样做合并操作,也就不要额外的内存存储空间,在算法复杂度和归并排序一样的情况下,有着更好的空间复杂度表现。
- 示例代码
<?php
/**
* Created by PhpStorm.
* User: liufeng
* Date: 2019/12/4
* Time: 11:14
*/
class Rand
{
public $randData = [];
public function __construct($num)
{
for ($i = 0; $i < $num; $i++) {
$this->randData[] = rand(0, 100);
}
}
}
function quick_sort(array $arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < $len; $i++) {
if ($arr[$i] > $pivot)
$right[] = $arr[$i];
else
$left[] = $arr[$i];
}
$left = quick_sort($left);
$right = quick_sort($right);
return array_merge($left, [$pivot], $right);
}
$rand = new Rand(10);
$randData = $rand->randData;
echo '<pre>';
print_r($randData);
/************** 计算使用时间 ******************/
$start_time = microtime(true);
print_r(quick_sort($randData));
$end_time = microtime(true);
echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';