PHP 排序算法之选中排序
发布时间:09/01 来源:未知 浏览:
关键词:
● 选中排序也是内部排序
● 排序思想:
第一次先随意选中一个数,就是在要排序的数组中选中一个元素和数组的其它元素比力。然后比力交流位置得到最小值或者最大值,然后再次在剩下的数组中,选中一个数和数组剩下的元素比力,最后得到第二个最小或最大的元素。顺次类推
● 示企图:
选中排序一共有数组大小 - 1 轮排序;每一轮排序又是一个轮回;先假定当前的这个数组就是最小数,然后和后面的元素顺次比力,假如发明有比当前数更小的数,就从新肯定最小数,并得到下标,当遍历到数组的最后时,就得到本轮最小数和下标,交流
1. 假设有一个待排序的数组 [3, 1, 15, 5, 20]
2. 随机选中一个元素,假设第一个就是最小的元素,拿 3 和数组剩下的元素比力,第一轮排序后得到最小元素 1
<?php $arr = [3, 1, 15, 5, 20]; $count = count($arr); //假设最小的元素就是第一个元素 $minIndex = 0; $min = $arr[0]; for ($j = $minIndex + 1; $j < $count; $j++) { if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值 $min = $arr[$j]; $minIndex = $j; } } $arr[$minIndex] = $arr[0]; $arr[0] = $min;
3. 再次选中一个假定最小值,与后面的元素一次比力,得到第二个最小值
<?php $arr = [1, 3, 15, 5, 20]; $count = count($arr); //假设最小的元素就是第二个元素 $minIndex = 1;//假设的最小元素的下表 $min = $arr[1];//假定最小元素的值 for ($j = $minIndex + 1; $j < $count; $j++) { if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值 $min = $arr[$j]; $minIndex = $j; } } if ($minIndex != 1) { $arr[$minIndex] = $arr[1];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交流 $arr[1] = $min;//元素下标交流 }
4. 以此类推,就可以使用双重 for 轮回,得到选中排序的算法如下:
public static function sortSelect(array $arr) :array { if (!is_array($arr)) { return ['message' => '$arr不是一个数组']; } $count = count($arr); if ($count <= 1) { return $arr; } for ($i = 0; $i < $count; $i++) { $minIndex = $i; $min = $arr[$i]; for ($j = $i + 1; $j < $count; $j++) { if ($min > $arr[$j]) {//选中的假定最小元素大于后面的元素 $min = $arr[$j];//把后面的最小元素赋值给假定的最小元素 $minIndex = $j;//把后面最小元素的坐标赋值给假定的最小元素 } } if ($minIndex != $i) {//假如在这个位置,一开端的假定最小元素的坐标被更换了,说明假定最小元素不是最小元素,那么发生交流 $arr[$minIndex] = $arr[$i];//交流最小元素,把最小元素和假定元素做交流 $arr[$i] = $min; } } return $arr; }
● 完全代码如下:
<?php class SelectSort { public static function select(array $arr):array { $count = count($arr); //假设最小的元素就是第二个元素 $minIndex = 0;//假设的最小元素的下表 $min = $arr[0];//假定最小元素的值 for ($j = $minIndex + 1; $j < $count; $j++) { if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值 $min = $arr[$j]; $minIndex = $j; } } if ($minIndex != 0) { $arr[$minIndex] = $arr[0];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交流 $arr[0] = $min;//元素下标交流 } var_dump($arr); $minIndex = 1;//假设的最小元素的下表 $min = $arr[1];//假定最小元素的值 for ($j = $minIndex + 1; $j < $count; $j++) { if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值 $min = $arr[$j]; $minIndex = $j; } } if ($minIndex != 1) { $arr[$minIndex] = $arr[1];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交流 $arr[1] = $min;//元素下标交流 } var_dump($arr); $minIndex = 2;//假设的最小元素的下表 $min = $arr[2];//假定最小元素的值 for ($j = $minIndex + 1; $j < $count; $j++) { if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值 $min = $arr[$j]; $minIndex = $j; } } if ($minIndex != 2) { $arr[$minIndex] = $arr[2];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交流 $arr[2] = $min;//元素下标交流 } var_dump($arr); return $arr; } public static function sortSelect(array $arr) :array { if (!is_array($arr)) { return ['message' => '$arr不是一个数组']; } $count = count($arr); if ($count <= 1) { return $arr; } for ($i = 0; $i < $count - 1; $i++) { $minIndex = $i; $min = $arr[$i]; for ($j = $i + 1; $j < $count; $j++) { if ($min > $arr[$j]) {//选中的假定最小元素大于后面的元素 $min = $arr[$j];//把后面的最小元素赋值给假定的最小元素 $minIndex = $j;//把后面最小元素的坐标赋值给假定的最小元素 } } if ($minIndex != $i) {//假如在这个位置,一开端的假定最小元素的坐标被更换了,说明假定最小元素不是最小元素,那么发生交流 $arr[$minIndex] = $arr[$i];//交流最小元素,把最小元素和假定元素做交流 $arr[$i] = $min; } } return $arr; } } $arr = [3, 1, 15, 5, 20]; var_dump(SelectSort::sortSelect($arr));
以上就是PHP 排序算法之选中排序的具体内容,更多请关注百分百源码网其它相关文章!