PHP 选择排序

2020-11-17 08:00 PHP在线

选择排序分为简单选择排序、树形选择排序和堆排序三类,此三类中,简单选择排序是最简单,也是最好理解的。


概念

选择排序 - Selection Sort:是一种简单直观的排序算法。顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完

步骤

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾

  3. 以此类推,直到所有元素均排序完毕

实现

方式一

<?php
class SelectionSort{ /** * 主运行方法 * * @return void */ public static function main(): void{ $random = self::random(); $array = self::sort($random); print_r($array); }
/** * 选择排序 * * @param array $array * * @return array */ public static function sort(array &$array): array{ $count = count($array); for ($i = 0; $i < $count; $i++) { $position = $i; for ($j = $i + 1; $j < $count; $j++) { if (self::compare($array[$position], $array[$j]) > 0) { $position = $j; } }
if ($position !== $i) { self::swap($array[$position], $array[$i]); } }
return $array; }
/** * 比较大小 * * @param int $x * @param int $y * * @return int */ private static function compare(int $x, int $y): int{ return $x <=> $y; }
/** * 互换位置 * * @param int $x * @param int $y * * @return void */ private static function swap(int &$x, int &$y): void{ if ($x !== $y) { $t = $x; $x = $y; $y = $t; } }
/** * 生成随机数组 * * @param int $low * @param int $high * @param int $num * * @return array */ private static function random(int $low = 1, int $high = 9999, int $num = 10): array{ $num = $num > $high ? $high : $num; $range = range($low, $high); $array = array_rand(array_flip($range), $num); shuffle($array);
return $array; }}
SelectionSort::main();
// 结果Array( [0] => 312 [1] => 1124 [2] => 1267 [3] => 1884 [4] => 2609 [5] => 4177 [6] => 4773 [7] => 7728 [8] => 8237 [9] => 8963)

方式二

树形选择排序 - Tree Selection Sort:又名锦标赛排序,是一种按照锦标赛的思想进行选择排序的方法

方式三

堆排序 - Heap Sort:是指利用堆这种数据结构所设计的一种排序算法。它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶

本文章转载自公众号:phpdaily

首页 - PHP 相关的更多文章: