迹忆客 专注技术分享

选择排序是一种简单直观的排序算法。其基本思想是在未排序的序列中选择一个最大（或最小）元素放到末尾（注意：这里是未排序序列的末尾，可以认为是有序序列的起始位置）。

下面通过一个简单的图例来了解一下这个选择的过程

首先记录选择第一个元素作为默认最大值，v存放值，p存放位置。

v = 10 ，p = 0

然后从第一个位置开始向后查找比10大的元素，找到以后替换v和p的值。

v = 12 ，p = 2

v = 30 ，p = 3

直到最后一个元素为止，30为该未排序序列中最大的元素。

然后交换30和最后一个元素，并且在下次选择中30不再参与比较。

第二次选择，v和p的初始值为0和10

v = 10 ， p = 0

经过查找，最后确定 v = 15 ， p = 3

然后交换15和5（因为30已不再参与排序）

15和30一样也不再参与排序。

然后依次按照上述过程进行选择交换，直到所有元素都有序为止

上面就是选择排序的整个过程。用文字表示其排序的步骤就是

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。

下面我们看选择排序的代码实现

/**
 * 交换函数
 */
function swap(&$arr,$a,$b){
    $t = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $t;
}
function SelectSort(&$arr){
    $end = count($arr)-1;
    do{
        $p = 0;
        for($i=0;$i<=$end;$i++){
            if($arr[$i]>$arr[$p]){
                $p = $i;
            }
        }
        swap($arr,$p,$end);
    }while(--$end>0);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
SelectSort($arr);
print_r($arr);

我们看上面的代码可以知道，选择排序很直观。其实现思路很简单，并不复杂。

但是有一点需要注意的是。虽然选择排序很简单，但是选择排序的效率较其他的排序算法低。其时间复杂度为O(n²)。所以说在应用中我们要根据实际情况去选择我们的排序算法。

希望本文对大家有所帮助。