PHP简单选择排序（Simple Selection Sort）算法学习

算法介绍

简单选择排序，也称直接选择排序，是一种简单直观的排序算法，其基本思想是：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的时间复杂度为 $O(n^2)$，不适用于大规模数据排序。但选择排序的思想被很多高级排序算法所引用，如堆排序和快速排序。

算法演示：

• 初始状态：[49, 38, 65, 97, 76, 13, 27, 49]
• 第一趟排序后：[13, 38, 65, 97, 76, 49, 27, 49]
• 第二趟排序后：[13, 27, 65, 97, 76, 49, 38, 49]
• 第三趟排序后：[13, 27, 38, 97, 76, 49, 65, 49]
• 第四趟排序后：[13, 27, 38, 49, 76, 97, 65, 49]
• 第五趟排序后：[13, 27, 38, 49, 49, 97, 65, 76]
• 第六趟排序后：[13, 27, 38, 49, 49, 65, 97, 76]
• 第七趟排序后：[13, 27, 38, 49, 49, 65, 76, 97]

PHP实现

/**
 * 简单选择排序
 *
 * @param array $arr 待排序数组
 * @return array 排序后的数组
 */
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) {
            // 交换位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp;
        }
    }
    return $arr;
}

示例说明

示例1

$arr = [49, 38, 65, 97, 76, 13, 27, 49];
$res = selectionSort($arr);
print_r($res);

输出：

Array
(
    [0] => 13
    [1] => 27
    [2] => 38
    [3] => 49
    [4] => 49
    [5] => 65
    [6] => 76
    [7] => 97
)

示例2

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

输出：

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
)

以上两个示例分别对一个无序数组和已经排好序的数组进行了简单选择排序。在第一个示例中，我们可以清晰地看到排序的过程，每次选择出最小的元素，并交换位置。在第二个示例中，由于数组已经排好序，所以只需要比较一次即可，算法复杂度为 $O(n)$。