周末抽时间整理下算法,完整导图可点击下面链接获取。
八种排序算法的php实现
代码如下 拷贝后可直接运行
先上个运行后的图
代码：（有的自己些的 有的根据网友整理）
<?php /** * Created by PhpStorm. * User: 百年黄沙 * Date: 2019/7/28/0020 * Time: 16:21:33 */
/** * Class Sort */ class Sort { /** * 直接选择排序 * * 选出剩余最小值放在左边 * 递归 * * @param $unsort * @return $mixed */ public static function ChoiceSort($unsort) { $len = count($unsort); $temp = $unsort; for ($i = 0; $i < $len; $i++) { $min = $temp[$i]; for ($j = $i; $j < $len; $j++) { if ($temp[$j] < $min) $min = $temp[$j]; } $key = array_keys($temp, $min); //最小值 if ($key[0] != $i) { $temp[$key[0]] = $temp[$i]; $temp[$i] = $min; } Sort::halt($unsort, $temp, $i + 1); } return $temp; } /** * 选择排序类 - 堆排序 这个有点难理解 可先看其他的 * * @param $unsort * @return array */ public static function HeapSort(&$arr) { $unsort = $arr; $count = count($arr); // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点) for ($i = floor($count / 2) - 1; $i >= 0; $i--) { Sort::CreateHeap($arr, $i, $count); } // 调整堆 for ($i = $count - 1; $i >= 0; $i--) { //将堆顶元素与最后一个元素交换 Sort::swap($arr, 0, $i); Sort::CreateHeap($arr, 0, $i - 1); Sort::halt($unsort,$arr,17-$i); } } //建立堆 public static function CreateHeap(&$arr, $start, $end) { $temp = $arr[$start]; //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0 for ($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1) { if ($j != $end && $arr[$j] < $arr[$j + 1]) { $j++; } if ($temp < $arr[$j]) { //将根节点设置为子节点的较大值 $arr[$start] = $arr[$j]; $start = $j; } } $arr[$start] = $temp; } /** * 插入类-直接插入排序 * * 从第一个元素开始，该元素可以认为已经排好序， * 取下一个，在已经排好序的序列中向前扫描， * 有元素大于这个新元素，将已经在排好序中的元素移到下一个位置， * 依次执行 * * @param $unsort * @return array */ public static function InsertSort($unsort) { $sort = array(); $len = count($unsort); $sort[0] = $unsort[0]; for ($i = 1; $i < $len - 1; $i++) { $sort[$i] = $unsort[$i]; for ($j = $i; $j > 0; $j--) { if ($sort[$j] < $sort[$j - 1]) { Sort::swap($sort, $j, $j - 1); } } Sort::halt($unsort,$sort,$i); } return $sort; } /** * 插入类-shell排序 * @param $unsort * @return array */ public static function ShellSort($unsort) { $count = count($unsort); $inc = $count; //增量 do { //计算增量 //$inc = floor($inc / 3) + 1; $inc = ceil($inc / 2); for ($i = $inc; $i < $count; $i++) { $temp = $unsort[$i]; //设置哨兵 //需将$temp插入有序增量子表 for ($j = $i - $inc; $j >= 0 && $unsort[$j + $inc] < $unsort[$j]; $j -= $inc) { $unsort[$j + $inc] = $unsort[$j]; //记录后移 } //插入 $unsort[$j + $inc] = $temp; } //增量为1时停止循环 } while ($inc > 1); return $unsort; } /** * 交换排序 - 冒泡排序 * * 重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。 * 走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。 * @param array $unsort * @return array */ public static function BubbleSort(array $unsort) { $sort = $unsort; $len = count($unsort); for ($i = 0; $i < $len - 1; $i++) { for ($j = 1; $j < $len; $j++) { if ($sort[$j] < $sort[$j - 1]) { Sort::swap($sort, $j, $j - 1); } } Sort::halt($unsort, $sort, $i + 1); } return $sort; } /** * 交换排序 - 快速排序 * * 通过设置一个初始中间值，来将需要排序的数组分成3部分， * 小于中间值的左边，中间值，大于中间值的右边， * 继续递归用相同的方式来排序左边和右边，最后合并数组 * * @param array $unsort * @return array */ public static function FastSort($unsort) { $len = count($unsort); if ($len <= 1) { return $unsort; } $middle = $unsort[0]; //取中间标尺 $left = array(); $right = array(); //todo 0 已被选做middle 注意 for ($i = 1; $i < $len; $i++) { if ($unsort[$i] < $middle) { $left[] = $unsort[$i]; } else { $right[] = $unsort[$i]; } } $left = Sort::FastSort($left); $right = Sort::FastSort($right); return array_merge($left, array($middle), $right); } /** * 归并排序 这个好像有点问题 * * 把序列分成元素尽可能相等的两半。 * 把两半元素分别进行排序。 * 把两个有序表合并成一个。 * * @param $unsort * @return array */ public static function MergeSort($unsort) { $sort = array(); $len = count($unsort); $divide = $len / 2; $part1 = array_slice($unsort, 0, $divide); $part2 = array_slice($unsort, $divide, $len - $divide); $one = Sort::FastSort($part1); $two = Sort::FastSort($part2); $lone = count($one); $ltwo = count($two); //todo for ($i = 0; $i < $lone; $i++) { if ($one[$i] < $two[$i]) { $sort[$i] = $one[$i]; } else { $sort[$i] = $two[$i]; } } return $sort; } /** * 桶排序 * * 桶排序的原理是先安排N+1个桶作为容器,若数据范围为N的话。 * 然后将测试数据(所需排序的数据)进行循环，放入对应的桶内。数据一定是在范围N内的。 * 最后,循环桶里的元素,并且输出,进行从大到小或从小到大的排序。 * * 浪费空间 * 无法比较浮点数值 * * @param $usort * @return array */ public static function BucketSort($unsort) { //取出值的范围 $len = max($unsort); //设置默认数组,默认值为0; for ($i = 0; $i <= $len; $i++) { $sort[$i] = 0; } for ($j = 0; $j < count($unsort); $j++) { $sort[$unsort[$j]]++; } foreach ($sort as $k => $v) { if (!empty($v)) { $arr[] = $k; } } return $arr; } /** * 公共交换位置方法 * @param array $arr 待换数据 * @param $a 位置1 * @param $b 位置2 */ public static function swap(array &$arr, $a, $b) { $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } /** * 优化显示 * @param $unsort * @param $arr * @param $i */ public static function halt($unsort, $arr, $i) { if ($i == 1) { echo "待 处 理 ：" . '[' . implode(" ", $unsort) . ']' . PHP_EOL; } echo "第" . $i . "次处理：" . '[' . implode(" ", $arr) . ']' . PHP_EOL; } } $uns = [14, 7, 23, 98, 43, 6, 8, 22]; $uns = [200, 13, 42, 34, 56, 23, 67, 365, 400, 54, 68, 3, 574, 5345, 645, 56778, 8978]; //选择排序 print_r(Sort::ChoiceSort($uns)); //堆排序 print_r(Sort::HeapSort($uns)); //插入排序 print_r(Sort::InsertSort($uns)); //shell 排序 print_r(Sort::ShellSort($uns)); //冒泡排序 print_r(Sort::BubbleSort($uns)); //快速排序 print_r(Sort::FastSort($uns)); //归并排序 print_r(Sort::MergeSort($uns)); //桶排序 print_r(Sort::BucketSort($uns));
持续更新