PHP排序算法之選擇排序

walterrwu 發(fā)布于2019-07-01 10:30 / 823人閱讀

摘要：二選擇排序原理在一列數(shù)字中，選出最小數(shù)與第一個位置的數(shù)交換。至此確定了前兩個位置上的數(shù)。示例代碼選擇排序?qū)崿F(xiàn)思路雙重循環(huán)完成，外層控制輪數(shù)，當(dāng)前的最小值。

二、選擇排序

　　原理：在一列數(shù)字中，選出最小數(shù)與第一個位置的數(shù)交換。然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。(以下都是升序排列，即從小到大排列)

　　舉例說明： $arr = array(6, 3, 8, 2, 9, 1);

　　第一輪：

　　第一次比較，第一個數(shù) 6 與（3, 8, 2, 9, 1)中 3 比較，6大，當(dāng)前最小數(shù)為3，位置為 1

　　　第二次比較，最小數(shù)字 3 與（3, 8, 2, 9, 1)中 8 比較，3小，當(dāng)前最小數(shù)為3，位置為 1

　　　第三次比較，最小數(shù)字 3 與（3, 8, 2, 9, 1)中 2 比較，3大，當(dāng)前最小數(shù)為2，位置為 3

　　　第四次比較，最小數(shù)字 2 與（3, 8, 2, 9, 1)中 9 比較，2小，當(dāng)前最小數(shù)為2，位置為 3

　　　第五次比較，最小數(shù)字 2 與（3, 8, 2, 9, 1)中 1 比較，2大，當(dāng)前最小數(shù)為1，位置為 5

　　第一輪比較完成后，確定最小數(shù)為1，小于第一個數(shù)6，交換位置上的數(shù)，交換后結(jié)果為 1 3 8 2 9 6

　　總結(jié)：第一輪比較，可以確定第一個位置的最小值。

　第二輪：

　　　第一次比較， 3與（8， 2, 9, 6）中 8 比較，3小，當(dāng)前最小數(shù)為3，位置為 1

　　　第二次比較， 3與（8， 2, 9, 6）中 2 比較，3大，當(dāng)前最小數(shù)為2，位置為 3

　　第三次比較， 2與（8， 2, 9, 6）中 9 比較，2小，當(dāng)前最小數(shù)為2，位置為 3

　　第四次比較， 2與（8， 2, 9, 6）中 6 比較，2小，當(dāng)前最小數(shù)為2，位置為 3

　　第二輪比較完成后，確定最小數(shù)為2，小于第二個數(shù)3，交換位置上的數(shù)，交換后結(jié)果為 1 2 8 3 9 6

　　總結(jié)：第二輪比較，可以確定第二個位置的最小值。至此確定了前兩個位置上的數(shù)。

　第三輪：

　　第一次比較， 8與（ 3, 9, 6）中 3 比較，8大，當(dāng)前最小數(shù)為3，位置為3

　　　第二次比較， 3與（ 3, 9, 6）中 9 比較，3小，當(dāng)前最小數(shù)為3，位置為3

　　第三次比較， 6與（ 3, 9, 6）中 6 比較，3小，當(dāng)前最小數(shù)為3，位置為3

　　　第三輪比較完成后，確定最小數(shù)為3，小于第三個數(shù)8，交換位置上的數(shù)，交換后結(jié)果為 1 2 3 8 9 6

　　總結(jié)：第三輪比較，可以確定第三個位置的最小值。至此確定了前三個位置上的數(shù)。

 第四輪：

　　第一次比較， 8與（ 9, 6）中 9 比較，8小，當(dāng)前最小數(shù)為8，位置為3

　　第二次比較， 8與（ 9, 6）中 6 比較，8大，當(dāng)前最小數(shù)為6，位置為5

　　第四輪比較完成后，確定最小數(shù)為6，小于第四個數(shù)8交換位置上的數(shù)，交換后結(jié)果為 1 2 3 6 9 8

　　總結(jié)：第四輪比較，可以確定第四個個位置的最小值。至此確定了前四個位置上的數(shù)。

第五輪：

　　第一次比較， 9與 8 比較，9大，當(dāng)前最小數(shù)為8，位置為5

    第五輪比較完成后，確定最小數(shù)為8，小于第五個數(shù)9，交換位置上的數(shù)，交換后結(jié)果為 1  2  3  6  8  9

　　總結(jié)：第五輪比較，可以確定第五個個位置的最小值。至此確定了前5個位置上的數(shù)。

綜合以上五輪比較，每一輪比較都可以確定一個位置，對于N個數(shù)，比較N-1輪可以確定N個位置上的數(shù)，因?yàn)榇_定了N-1個位置，最后一個位置也就確定了。

示例代碼：
選擇排序實(shí)現(xiàn)思路雙重循環(huán)完成，外層控制輪數(shù)，當(dāng)前的最小值。內(nèi)層控制的比較次數(shù)
for ($i=0; $i < count($arr)-1; $i++) { //$i 當(dāng)前最小值的位置，需要參與比較的元素

$p = $i;//先假設(shè)最小的值的位置

for ($j=$i+1; $j < count($arr); $j++) { //$j 當(dāng)前都需要和哪些元素比較，$i 后邊的。
    if($arr[$p] > $arr[$j])
    {
        $p = $j;
    }
}

if($p != $i)
{
    $tmp = $arr[$p];
    $arr[$p] = $arr[$i];
    $arr[$i] = $tmp;
}

}
var_dump($arr);