選擇排序select sorting
● 選擇排序也是內部排序
● 排序想法：
第一次先隨便選擇一個數，就是在要排序的陣列中選擇一個元素和陣列的其它元素比較。然後比較交換位置得到最小值或最大值，然後再次在剩下的陣列中，選擇一個數和陣列剩下的元素比較，最後得到第二個最小或最大的元素。依序類別推
● 示意圖：
選擇排序一共有數組大小- 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 排序演算法之選擇排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
