迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

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

发布时间: 2016-04-12 作者: 迹忆 浏览次数:

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

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

首先记录选择第一个元素作为默认最大值,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²)。所以说在应用中我们要根据实际情况去选择我们的排序算法。

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

赞助
迹忆博客

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: