PHP排序算法系列之直接选择排序详解

一、前言

本文将详细讲解直接选择排序，直接选择排序是一个简单但常用的排序算法，对初学者来说是个很好的入门算法，代码也比较易懂。

二、算法原理

直接选择排序，是一种比较简单直观的排序算法。其基本思想为：将待排序的序列划分为已排序和未排序两部分，从未排序的序列中选择最小的元素，将其插入已排序序列的末尾，直到所有元素均排序完毕。

三、算法步骤

1.取数组中的第一个元素，作为已排序数组。

2.在未排序数组中寻找最小值，记录其下标。

3.将找到的最小值与未排序数组的第一个元素交换位置，将交换后的第一个元素作为已排序数组的下一个元素。

4.重复步骤 2 和 步骤 3，直到未排序数组的元素全部移动到已排序数组。

5.当未排序数组的元素已全部移动到已排序数组时，排序完成。

四、代码实现

PHP代码实现如下：

function selectionSort(array $arr): array
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }

        if ($minIndex != $i) {
            [$arr[$i], $arr[$minIndex]] = [$arr[$minIndex], $arr[$i]];
        }
    }
    return $arr;
}

五、示例说明

示例一：

$arr = [3, 4, 2, 1, 5];
$res = selectionSort($arr);
var_dump($res);

输出结果为：

array(5) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
  [3]=>
  int(4)
  [4]=>
  int(5)
}

示例二：

$arr = [100, 5, 20, 55, 13, 28, 67, 33, 99, 88];
$res = selectionSort($arr);
var_dump($res);

输出结果为：

array(10) {
  [0]=>
  int(5)
  [1]=>
  int(13)
  [2]=>
  int(20)
  [3]=>
  int(28)
  [4]=>
  int(33)
  [5]=>
  int(55)
  [6]=>
  int(67)
  [7]=>
  int(88)
  [8]=>
  int(99)
  [9]=>
  int(100)
}

六、总结

直接选择排序是一种简单而实用的排序算法，其代码实现也相对简单易懂，适合初学者进行学习。但在实际应用中，如果数据量过大，其时间复杂度较高，不建议使用直接选择排序。