排序算法--选择排序

        选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

        表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

        算法描述：

        给定一个数组，从小到大排序首先找到数组中最小的那个元素，其次将它和数组中的第一个元素交换位置（如果第一个就是最小那么他就和自己交换），再次，在剩下的元素中找到最小元素将它与数组的第二个元素交换位置，如此往复直到将整个数组排序这种排序方法就叫做选择排序

        n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录
 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

        动图演示：

        代码实现：

function selectSort($arr) {
    $len=count($arr);

    for($i=0;  $i<$len-1;  $i++) {    //控制循环长度
        $min = $i;                    //先假设最小的值的位置（记录下标）

        for($j=$i+1;  $j<$len; $j++) {    //!!!!控制双层循环的长度!!!!!
            if($arr[$j] < $arr[$min]) {    
                $min = $j;                //比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。
        if($min != $i) {
            $temp      = $arr[$i];
            $arr[$i]   = $arr[$min];
            $arr[$min] = $temp;
        }
    }
    //返回最终结果
    return $arr;
}

维基百科：https://en.wikipedia.org/wiki/Selection_sort 

本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn

• 上一篇： 排序算法--插入排序
• 下一篇： PHP设计模式-工厂模式（下）