PHP排序算法之簡單選擇排序(Simple Selection Sort)實例分析

更新時間：2018年04月20日 11:57:45 作者：LSGOZJ

這篇文章主要介紹了PHP排序算法之簡單選擇排序(Simple Selection Sort),結(jié)合實例形式較為詳細(xì)的分析了簡單選擇排序算法的原理與相關(guān)實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了PHP排序算法之簡單選擇排序(Simple Selection Sort)。分享給大家供大家參考，具體如下：

基本思想：

通過 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);

運行結(jié)果：

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

復(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)》，在此僅作記錄，方便以后查閱，大神勿噴！

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《php排序算法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計有所幫助。

您可能感興趣的文章: