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

复杂度分析：

在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。

最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从小到大顺序排列，则需要移动记录的次数最多为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如何实现选择排序”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。