PHP簡單選擇排序案例詳解

這次帶給大家PHP簡單選擇排序案例詳解，PHP簡單選擇排序的注意事項有哪些，以下就是實戰案例，一起來看一下。

基本概念：

透過n - i 次關鍵字間的比較，從n - i 1 個記錄中選出關鍵字最小的記錄，並且和第i （1 <= i <= n） 個記錄交換，執行n-1趟後就完成了記錄序列的排序。

演算法實作：

<?php
//简单选择排序
//交换函数
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);

執行結果：

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)
}

##複雜度分析：

在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。

最壞情況下，即待排序記錄初始狀態是依第一筆記錄最大，之後的記錄從小到大順序排列，則需要移動記錄的次數最多為3（n-1）。簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是(n-1) (n-2) … 2 1=n(n-1)/2，即進行比較操作的時間複雜度為

O(n^2)，進行移動操作的時間複雜度為O(n)。

簡單選擇排序是不穩定排序。

相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！

推薦閱讀：

PHP快速排序演算法使用步驟詳解

#PHP基數排序使用步驟詳解

以上是PHP簡單選擇排序案例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！