黑马程序员技术交流社区

标题: 选择排序法 [打印本页]

---

作者: 董事长    时间: 2016-11-14 16:35
标题: 选择排序法
<?php
//选择排序法思路： 每次选择一个相应的元素，然后将其放到指定的位置
$arr = array(1,43,54,62,21,66,32,78,36,76,39);
function select_sort($arr) {
        //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
        //$i 当前最小值的位置， 需要参与比较的元素
        for($i=0, $len=count($arr); $i<$len-1; $i++) {
                //先假设最小的值的位置
                $p = $i;
                //$j 当前都需要和哪些元素比较，$i 后边的。
                for($j=$i+1; $j<$len; $j++) {
                        //$arr[$p] 是 当前已知的最小值
                        if($arr[$p] > $arr[$j]) {
                                //比较，发现更小的,记录下最小值的位置；并且在下次比较时，
                                // 应该采用已知的最小值进行比较。
                                $p = $j;
                        }
                }
                //已经确定了当前的最小值的位置，保存到$p中。
                //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
                if($p != $i) {
                        $tmp = $arr[$p];
                        $arr[$p] = $arr[$i];
                        $arr[$i] = $tmp;
                }
        }
        //返回最终结果
        return $arr;
}
$select = select_sort($arr);
echo "<pre>";
var_dump($select);

---

作者: mfsara    时间: 2016-11-17 08:11
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2