php实现选择排序

选择排序的基本原理

选择排序是一种简单直观的排序算法，其核心思想是每次从未排序的部分选出最小（或最大）的元素，放到已排序部分的末尾。重复这一过程直到所有元素有序。

PHP实现选择排序

以下是PHP实现选择排序的代码示例：

function selectionSort($array) {
    $length = count($array);
    for ($i = 0; $i < $length - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $length; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }
        if ($minIndex != $i) {
            $temp = $array[$i];
            $array[$i] = $array[$minIndex];
            $array[$minIndex] = $temp;
        }
    }
    return $array;
}

// 示例用法
$unsortedArray = [64, 25, 12, 22, 11];
$sortedArray = selectionSort($unsortedArray);
print_r($sortedArray);

代码解析

1. 外层循环：控制排序的轮次，每次确定一个最小元素的位置。
2. 内层循环：在未排序部分中查找最小元素的索引。
3. 交换操作：将找到的最小元素与当前未排序部分的第一个元素交换位置。

时间复杂度分析

• 最好情况：O(n²)
• 最坏情况：O(n²)
• 平均情况：O(n²)

选择排序的时间复杂度始终为O(n²)，因为它无论如何都需要进行n(n-1)/2次比较。

优化思路

虽然选择排序的时间复杂度固定，但可以通过以下方式优化实际运行时间：

1. 减少交换次数：每次循环只交换一次元素。
2. 双向选择排序：同时寻找最小和最大元素，减少循环次数。