常用的排序算法系列
选择排序以及优化
选择排序也是一种常用的简单的排序算法，虽然算法的复杂度是和冒泡一样都是O（n^2）,但性能还是稍微好一些的，在一些简单的场景中选择排序非常好用。
假设当前需要进行排序，选择排序的核心思路是，找到一个最大或者最小的标记位，将其与当前需要排序的位置交换他们的值，这样的交换就会比冒泡更加有效率。
举例说明：
假设当前需要排序的数组如下：
[ 34, 5, 555,14, 88, 5 ]
首先我们要用一个循环来遍历这个数组，用来做排序的位置交换。
默认呢，假设当前取到的第一个数字是最小的，我们记录下编号即可，后面找到真正的最小值编号我们再更新即可。
第一次我们取第一个数 34 作为当前的最小值，记录下他的 最小值编号 0。
接着，我们要再用一个循环，去找数组后面部分的需要交换的位置（也就是找到真正的最小值编号），当前排序的，是编号0位置，因此我们从编号1开始往后找，如果发现后面有小于等于编号位置的值，我们就更新这个最小值编号。
往后找，发现 5 比 34 小，于是最小值编号就变成了1 。
继续往后找，发现编号5的5等于当前最小值5，于是最小值编号就变成了5 。
最后，我们来判断一下最小值编号和最开始有没有变化，如果有变化，说明找到了一个更小的数再后面，那就应该进行交换操作把它弄到前面来。如果没有变化，就是说后面没有更小的了，我们不需要交换了。往后开始排下一个位置即可。
此时最小值编号是5，已经不等于最开始我需要排序的位置0了，所以我们进行一个交换，得到的结果为：
[ 34, 5, 555,14, 88, 5 ] --> 排序一次后–> [ 5, 5, 555,14, 88, 34 ]
完成之后，我们排下一个位置，也就是位置编号1，重复上面的步骤即可。
位置1的5，找不到更小的,不理
[ 5,5, 555,14, 88, 34 ]
位置2的555，与位置5的34交换
[ 5, 5, 555,14, 88, 34 ] --> [ 5, 5, 34 ,14, 88, 555 ]
位置3的14，找不到更小的，不理
[ 5, 5, 34 ,14, 88, 555 ]
位置4的88，找不到更小的，不理
[ 5, 5, 34 ,14, 88, 555 ]
位置5的555，找不到更小的。不理
[ 5, 5, 34 ,14, 88,** 555** ]
这样我们就完成了排序的过程。写程序的时候要特别注意这个编号的概念，我们的目的是为了找编号，然后将对应标号的值去做交换，并不是直接去用这个最小值。
PHP实现排序过程如下:
优化
可以看出，我们通过找最小值的下标编号，来减少中间不必要的数组元素交换操作，而我们每次只是标记一个最小的值，通过一个方向来排序。
因为最大最小其实是一个对称的操作判断，有没有方式可以更快完成这个流程呢？
当然是有的，我们可以把原来单路的选择排序，改成双路的，每次标记一个最小和一个最大的值，通过两个方向来排序。
每次排序的进行两个标记，一个是找出范围里的最大值，另一个是找出范围里的最小值，相当于是同时在做一个两个方向的排序，每次排序能稳定的排出来两个值。
下一次循环的时候，缩减查找的排序范围，左边界的值加一，右边界的值减一，直到相遇。
这里其实就有一点点快排的味道出来了，快排是有分治思想在里面的，所以会更加快。
PHP排序过程如下：
代码
PHP选择排序
<?php
/**
* Created by PhpStorm.
* User: L
* Date: 2018-9-27
* Time: 11:29
*/
$ar = [5, 8, 6, 4, 12, 5, 3, 1, 89, 54];
echo "input: <br/>";
print_r(json_encode($ar));
echo "<br/>";
selection($ar);
echo "result: <br/>";
print_r(json_encode($ar));
echo "<br/>";
/** 选择排序
* @param array $ar
* @param null $len
*/
function selection(array & $ar, $len = null)
{
if ($len === null) {
$len = sizeof($ar);
}
for ($i = 0; $i < $len - 1; $i++) {
$min = $i; //consider i as min_index
for ($j = $i + 1; $j < $len; $j++) {//find min_index
if($ar[$j]<=$ar[$min]){
$min = $j;
}
}
//check min_index and swap
if($min!=$i){//changeSelectionSort.php
$t = $ar[$i];
$ar[$i]=$ar[$min];
$ar[$min] = $t;
}
echo "after 1 times: <br/>";
print_r(json_encode($ar));
echo "<br/>";
}
}
PHP选择排序-双路优化
<?php
/**
* Created by PhpStorm.
* User: L
* Date: 2018-9-27
* Time: 11:29
*/
$ar = [5, 8, 6, 4, 12, 5, 3, 1, 89, 54];
echo "input: <br/>";
print_r(json_encode($ar));
echo "<br/>";
selection($ar);
echo "result: <br/>";
print_r(json_encode($ar));
echo "<br/>";
/** 优化的选择排序
* @param array $ar
* @param null $len
*/
function selection(array & $ar, $len = null)
{
if ($len === null) {
$len = sizeof($ar);
}
for ($left = 0, $right = $len - 1; $left < $right; $left++, $right--) {
$min = $left; //consider left as min_index and max_index
$max = $right;
for ($j = $left + 1; $j <= $right; $j++) {//find min_index max_index
if ($ar[$j] <= $ar[$min]) {
$min = $j;
}
if ($ar[$j] >= $ar[$max]) {
$max = $j;
}
}
//check min_index and swap
if ($min != $left) {
$t = $ar[$left];
$ar[$left] = $ar[$min];
$ar[$min] = $t;
}
if ($max != $right) {
$t = $ar[$right];
$ar[$right] = $ar[$max];
$ar[$max] = $t;
}
echo "after 1 times: <br/>";
print_r(json_encode($ar));
echo "<br/>";
}
}