PHP常用算法
2019-12-05 本文已影响0人
牍中玉的小木屋
基于选择的排序算法
常见的基于选择的排序算法有：冒泡排序、插入排序、选择排序、归并排序和快速排序，我们在选在排序算法的时候，通常会根据以下几个维度来考虑：
- 时间复杂度
- 空间复杂度（对内存空间的消耗）
- 算法的稳定性（如果待排序的序列中存在值相等的元素，经过排序之后，相同元素之间原有的先后顺序不变）
介绍一个网站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) . ' 微秒';
