PHP實現簡單選擇排序算法詳解與示例代碼

什麼是簡單選擇排序

簡單選擇排序是一種直觀且常用的排序算法，能夠有效處理各種數據。其核心思想是：每次從待排序的元素中選出最小值，並將其放置到已排序序列的末尾。具體過程為：第一次在整個數組中選出最小元素與第一個位置交換，第二次從剩餘元素中選最小值與第二個位置交換，依此類推，直到所有元素排序完成。

算法步驟

首先獲取數組長度n，然後進行n-1輪選擇操作。每一輪選擇從未排序部分找到最小值，並將其與當前輪起始位置元素交換，實現局部有序，最終完成整體排序。

算法演示

以下為PHP實現的簡單選擇排序示例代碼，便於理解算法具體執行過程：

 function selectionSort(&$arr)
{
    $len=count($arr);
    for($i=0;$i<$len-1;$i++)
    {
        $min=$i; // 假設當前元素為最小值位置
        for($j=$i+1;$j<$len;$j++) // 從後續元素中查找更小值
        {
            if($arr[$j]<$arr[$min])
            {
                $min=$j; // 更新最小值位置
            }
        }
        if($min!=$i) // 位置變化時交換元素
        {
            $temp=$arr[$min];
            $arr[$min]=$arr[$i];
            $arr[$i]=$temp;
        }
    }
}

算法分析

時間複雜度

簡單選擇排序需要進行n-1輪選擇，每輪在剩餘元素中找最小值，因此比較次數為約n²/2，移動次數依賴初始數據順序。總的時間複雜度為O(n²)。儘管如此，當數據量較小或基本有序時，該算法仍具一定實用性。

空間複雜度

該算法僅使用了一個臨時變量來輔助交換，空間開銷極小，空間複雜度為O(1)。

算法穩定性

簡單選擇排序是不穩定的排序算法。相同元素在排序過程中可能因交換位置而改變相對順序。例如序列5 8 5 2 9，第一輪將最小元素2與第一個元素5交換後，相同的5的位置順序就被打亂。