本文實例為大家分享了PHP簡單選擇排序的具體代碼，供大家參考，具體內(nèi)容如下
基本思想：
通過 n - i 次關(guān)鍵字間的比較，從 n - i + 1 個記錄中選出關(guān)鍵字最小的記錄，并和第 i （1 <= i <= n） 個記錄交換，執(zhí)行n-1趟 后就完成了記錄序列的排序。
算法實現(xiàn)：
<?php
//簡單選擇排序
//交換函數(shù)
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//簡單選擇排序算法
function SelectSort(array &$arr){
$count = count($arr);
for($i = 0;$i < $count - 1;$i ++){
//記錄第$i個元素后的所有元素最小值下標(biāo)
$min = $i;
for($j = $i + 1;$j < $count;$j ++){
if($arr[$j] < $arr[$min]){
$min = $j;
}
}
if($min != $i){
swap($arr,$min,$i);
}
}
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);
復(fù)雜度分析：
在簡單選擇排序過程中，所需移動記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動記錄。
最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動記錄的次數(shù)最多為3（n-1）。簡單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)。當(dāng)i=1時，需進(jìn)行n-1次比較；當(dāng)i=2時，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時間復(fù)雜度為O(n^2)，進(jìn)行移動操作的時間復(fù)雜度為O(n)。
簡單選擇排序是不穩(wěn)定排序。
本篇博客參考自《大話數(shù)據(jù)結(jié)構(gòu)》，在此僅作記錄，方便以后查閱，大神勿噴！
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持。
【網(wǎng)站聲明】本站除付費(fèi)源碼經(jīng)過測試外，其他素材未做測試，不保證完整性，網(wǎng)站上部分源碼僅限學(xué)習(xí)交流，請勿用于商業(yè)用途。如損害你的權(quán)益請聯(lián)系客服QQ：2655101040 給予處理，謝謝支持。