排序算法--选择排序

        选择排序(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趟结束,数组有序化了。

        动图演示

        冷暖自知一抹茶ck

        代码实现:

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 


冷暖自知一抹茶ck
请先登录后发表评论
  • 最新评论
  • 总共0条评论