本文實例為大家分享了PHP簡單選擇排序的具體代碼,供大家參考,具體內(nèi)容如下
基本思想:
通過 n - i 次關鍵字間的比較,從 n - i + 1 個記錄中選出關鍵字最小的記錄,并和第 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個元素后的所有元素最小值下標 $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);
復雜度分析:
在簡單選擇排序過程中,所需移動記錄的次數(shù)比較少。最好情況下,即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了,則不需要移動記錄。
最壞情況下,即待排序記錄初始狀態(tài)是按第一條記錄最大,之后的記錄從小到大順序排列,則需要移動記錄的次數(shù)最多為3(n-1)。簡單選擇排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關。當i=1時,需進行n-1次比較;當i=2時,需進行n-2次比較;依次類推,共需要進行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2,即進行比較操作的時間復雜度為O(n^2),進行移動操作的時間復雜度為O(n)。
簡單選擇排序是不穩(wěn)定排序。
本篇博客參考自《大話數(shù)據(jù)結(jié)構》,在此僅作記錄,方便以后查閱,大神勿噴!
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。