php选择排序

sisophon 2019-09-30 PM 25℃ 0条

选择排序(Selection sort)是一种简单直观的排序算法。

原理:

a.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

b.再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

c. 重复第二步,直到所有元素均排序完毕。

代码:

$arr = array(8,6,9,2,7,1);
for ($i=0; $i < count($arr)-1; $i++) { //$i 当前最小值的位置, 需要参与比较的元素

    $p = $i;//先假设最小的值的位置
    
    for ($j=$i+1; $j < count($arr); $j++) { //$j 当前都需要和哪些元素比较,$i 后边的。
        if($arr[$p] > $arr[$j])
        {
            $p = $j;
        }
    }

    if($p != $i)
    {
        $tmp = $arr[$p];
        $arr[$p] = $arr[$i];
        $arr[$i] = $tmp;
    }
}

解析:

第一轮:

第一次

p j

0 1

$arr[$p] $arr[$j]

8 6

8>6 所以最小值的下标变为$j 即$p=$j=1

第二次:

p j

1 2

$arr[$p] $arr[$j]

6 9

6<9 所以最小值的下标还是$p 即$p=1

第三次:

p j

1 3

$arr[$p] $arr[$j]

6 2

6>2 所以最小值的下标变为$j 即$p=$j=3

第四次:

p j

3 4

$arr[$p] $arr[$j]

2 7

2<7 所以最小值的下标还是$p 即$p=3

第五次:

p j

3 5

$arr[$p] $arr[$j]

2 1

2>1 所以最小值的下标为$j 即$p=$j=5

第一轮置换以后结果为:1 6 9 2 7 8

以此类推 最后结果为1 2 6 7 8 9

复杂度:

选择排序是冒泡排序的改进,同样选择排序无论序列是怎样的都是要比较n(n-1)/2次的,最好、最坏、平均时间复杂度也都为O(n²),需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)。

标签: PHP

非特殊说明,本博所有文章均为博主原创。

上一篇 php冒泡排序
下一篇 php插入排序

评论啦~