排序算法学习之路——选择排序

Z时代
2024-01-10
分类：综合

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

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

首先记录选择第一个元素作为默认最大值，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）重复第二步，直到所有元素均排序完毕。

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

/**
 * 交换函数
 */
functionswap(&$arr,$a,$b){
$t = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $t;
}
functionSelectSort(&$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);