你可能会用到的PHP算法&数据结构
Sonder
2019-10-17
7503字
19分钟
浏览 (5.8k)
1. 数组关联id结合
有评论的list和回复的list，其中回复的id等于评论的mid；通过这两个关联，让回复的list放在评论某个数组里面。
private function comment_and_reply($comment_list,$reply_list){
foreach($comment_list as &$v) {
$v['replay'] = [];
foreach ($reply_list as $vv){
if ($v['id'] == $vv['mid']){
array_push($v['replay'], $vv);
}
}
}
unset($v);
return $comment_list;
}2. 递归；通过自己找到儿子
public function getchildrenid($table,$cid){
$table_res=db($table)->select();
if($table_res){
return $this->_getchildrenid($table_res,$cid);
}
}
private function _getchildrenid($table_res,$cid){
static $arr=array();
foreach($table_res as $k=>$v){
if($v['pid'] == $cid){
$arr[]=$v['id'];
//防止无下限循环
$this->_getchildrenid($table_res,$v['id']);
}
}
return $arr;
}3. 选择排序（Selection Sort）
选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
/**
* 选择排序 每次选取最小的一个数字与当前数字交换
* @param $arr
* @return array
*/
function selectSort($arr)
{
if (empty($arr) || !is_array($arr)) {
return $arr;
}
$arr = array_values($arr);
// 数组长度
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
// 最小下标
$minIndex = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
// 选取最小数字的下标
$minIndex = $j;
}
}
// 如果最小数字的下标等于当前下标，继续循环
if ($minIndex == $i) {
continue;
}
// 交换数据
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}4. 插入排序（Insertion Sort）
插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。
第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j 指针向左移动一个位置，不断进行以上操作。
//插入排序
function insertSort($arr)
{
if (empty($arr) || !is_array($arr)) {
return $arr;
}
$arr = array_values($arr);
// 数组长度
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
// 当前数字(刚抓的扑克牌)
$curr = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
// 当前数字如果单元前面一个的时候直接结束循环，因为前面的已经排好了
if ($curr > $arr[$j]) {
break;
}
// 前面所有数字往后移动
$arr[$j + 1] = $arr[$j];
}
// 因为上面循环最后$j--了，所以这里把$j
$arr[$j + 1] = $curr;
}
return $arr;
}5.冒泡排序（Bubble Sort）
通过从左到右不断交换相邻逆序的相邻元素，在一轮的交换之后，可以让未排序的元素上浮到右侧。
在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。
function bubbleSort($arr)
{
if (empty($arr) || !is_array($arr)) {
return $arr;
}
$arr = array_values($arr);
// 标识位
$flag = false;
// 数组长度
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$flag = true;
}
}
if (!$flag) {
break;
}
}
return $arr;
}6. 希尔排序（Shell Sort）
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
<?php
function shellSort($arr) {
$len = count($arr);
for ($gap = floor($len / 2); $gap > 0; $gap = floor($gap / 2)) {
for($i = $gap; $i < $len; $i++) {
for($j = $i - $gap; $j >= 0; $j -= $gap) {
if ($arr[$j + $gap] < $arr[$j]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+$gap];
$arr[$j + $gap] = $temp;
}
}
}
}
return $arr;
}
// 测试
$arr = range(1, 10);
shuffle($arr);
echo "排序前：";
print_r($arr);
echo "</br>";
echo "排序后：";
$res = shellSort($arr);
print_r($res);7. 归并排序（Merge Sort）
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
//归并排序
function mergeSort(&$arr, $left, $right) {
if(empty($arr) || !is_array($arr)) {
return $arr;
}
$arr = array_values($arr);
if ($left < $right) {
// 找出中间索引
$mid = floor(($left + $right) / 2);
// 对左边数组进行递归
mergeSort($arr, $left, $mid);
// 对右边数组进行递归
mergeSort($arr, $mid + 1, $right);
// 合并
merge($arr, $left, $mid, $right);
}
}
// 将两个有序数组合并成一个有序数组
function merge(&$arr, $left, $mid, $right) {
$i = $left; // 左数组的下标
$j = $mid + 1; // 右数组的下标
$temp = array();// 临时合并数组
// 扫描第一段和第二段序列，直到有一个扫描结束
while ($i <= $mid && $j <= $right) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if ($arr[$i] < $arr[$j]) {
$temp[] = $arr[$i];
$i++;
} else {
$temp[] = $arr[$j];
$j++;
}
}
// 比完之后，假如左数组仍有剩余，则直接全部复制到 temp 数组
while ($i <= $mid) {
$temp[] = $arr[$i];
$i++;
}
// 比完之后，假如右数组仍有剩余，则直接全部复制到 temp 数组
while ($j <= $right) {
$temp[] = $arr[$j];
$j++;
}
// 将合并序列复制到原始序列中
for($k = 0; $k < count($temp); $k++) {
$arr[$left + $k] = $temp[$k];
}
}
$arr= ["2","3","5","47","21","22","4","30","148","121","50"];
mergeSort($arr, 0, count($arr) - 1);
print_r($arr);8. 快速排序（Quick Sort）
/**
* 快速排序 分开大小集合，然后在递归排序
* @param $arr
* @return array
*/
function quickSort($arr)
{
if (empty($arr) || !is_array($arr)) {
return $arr;
}
$arr = array_values($arr);
// 第一个作为中间值
$m = $arr[0];
// 小于中间值$m的放左边$left,反之放右边$right
$left = $right = [];
// 数组长度
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
if ($arr[$i] < $m) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
$left = quickSort($left);
$right = quickSort($right);
return array_merge($left, array($m), $right);
}9.堆排序（Heap Sort）
排序过程可知：若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。
<?php
// 堆排序（大顶堆）
function heapSort(&$arr) {
$len = count($arr);
// 先将数组构造成大根堆
for ($i = floor($len / 2) - 1; $i >= 0; $i--) {
adjustHeap($arr, $i, $len);
}
// 调整堆结构+交换堆顶元素与末尾元素
for ($j = $len - 1; $j > 0; $j--) {
swap($arr, 0, $j); // 将堆顶元素与末尾元素进行交换
adjustHeap($arr, 0, $j); // 重新对堆进行调整
}
}
// 调整堆
function adjustHeap(&$arr, $i, $length) {
$temp = $arr[$i]; // 先取出当前元素
for ($k = 2 * $i + 1; $k < $length; $k = 2 * $k + 1) {// 左孩子2 * i+1，右孩子2∗i + 2
if ($k + 1 < $length && $arr[$k] < $arr[$k + 1]) {// 如果左子结点小于右子结点，k指向右子结点
$k ++;
}
if ($temp < $arr[$k]) {
$arr[$i] = $arr[$k]; // 将根节点设置为子节点的较大值
$i = $k; // 继续往下
} else {
break; // 已经满足大根堆
}
}
$arr[$i] = $temp; // 将temp值放到最终的位置
}
// 交换2个值
function swap(&$arr, $a, $b) {
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
// 测试
$arr = array(49, 38, 65, 97, 76, 13, 27, 50);
heapSort($arr);
print_r($arr);