程序员算法入门—排序选择

选择排序

原理:假设有一组数组,从里面找出最小数与第一个位置的数交换,再者在剩下的数里面找出最小的数与第二位置的数交换,以此类推,倒数第二个数与最后一个数比较后,从小到大的顺序一一排列。

例如:  $arr = array(6,3,8,2,9,1);

$arr数组里有6个数据,注意  比较轮数 和 每轮比较次数

  1. 第一个数6和(3,8,2,9,1)中的3比较,结果:6大,当前最小数为3,位置为1

  2. 最小数字3和(3,8,2,9,1)中的8比较,结果:3小,当前最小数为3,位置为1

  3. 最小数字3和(3,8,2,9,1)中的2比较,结果:3大,当前最小数为2,位置为3

  4. 最小数字2和(3,8,2,9,1)中的9比较,结果:2小,当前最小数为2,位置为3

  5. 最小数字2和(3,8,2,9,1)中的1比较,结果:2大,当前最小数为1,位置为5

①轮总结:

1、确定最小数为1,小于第一个数6,交换这两个数的位置,此时结果为 1 3 8 2 9 6

2、可以确定第一个位置的最小值

  1. 第二个数3和(8,2,9,6)中的8比较,结果:3小,当前最小数为3,位置为1

  2. 最小数字3和(8,2,9,6)中的2比较,结果:3大,当前最小数为2,位置为3

  3. 最小数字2和(8,2,9,6)中的9比较,结果:2小,当前最小数为2,位置为3

  4. 最小数字2和(8,2,9,6)中的6比较,结果:2小,当前最小数为2,位置为3

②轮总结:

1、确定最小数为2,小于第二个数3,交换这两个数的位置,此时结果为 1 2 8 3 9 6

2、可以确定第二个位置的最小值,至此确定了前两个位置上的数

  1. 第三个数8和(3,9,6)中的3比较,结果:8大,当前最小数为3,位置为3

  2. 最小数字3和(3,9,6)中的9比较,结果:3小,当前最小数为3,位置为3

  3. 最小数字3和(2,9,6)中的6比较,结果:3小,当前最小数为3,位置为3

③轮总结:

1、确定最小数为3,小于第三个数8,交换这两个数的位置,此时结果为 1 2 3 8 9 6

2、可以确定第三个位置的最小值,至此确定了前三个位置上的数

  1. 第四个数8和(9,6)中的9比较,结果:8小,当前最小数为8,位置为3

  2. 最小数字8和(9,6)中的6比较,结果:8大,当前最小数为6,位置为5

④轮总结:

1、确定最小数为6,小于第四个数8,交换这两个数的位置,此时结果为 1 2 3 6 9 8

2、可以确定第四个位置的最小值,至此确定了前四个位置上的数

  1. 第五个数9和8比较,结果:9大,当前最小数为8,位置为5

⑤轮总结:

1、确定最小数为8,小于第五个数9,交换这两个数的位置,此时结果为 1 2 3 6 8 9

2、可以确定第五个位置的最小值,至此确定了前五个位置上的数

 

经过①②③④⑤轮比较,得出结论:

对于一个长度为N的数组,我们需要排序 N-1 轮,每N-1轮比较都可以确定N个位置上的数。

 

用时间复杂度说:

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0。当序列反序时,移动次数最多,为3N (N - 1) /  2。

选择排序总的平均时间复杂度为:O(n2) 。

 

ex:

<?php

function xzpx($arr) {

    //定义中间变量
    $temp = 0;
    $count = count($arr);
    for($i=0;$i<$count-1;$i++) { //轮数
        //定义最小位置
        $minIndex = $i;
        for($j=$i+1;$j<$count;$j++) {
            if($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        if($i != $minIndex) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp;
        }
    }
    return $arr;
}

$arr = array(6,3,8,2,9,1);
$res = xzpx($arr);
var_dump($res);

参考链接:

https://www.cnblogs.com/wgq123/p/6529450.html

http://www.cnblogs.com/shen-hua/p/5422676.html

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注