PHP排序算法之简单选择排序(Simple Selection Sort)实例

1.什么是简单选择排序

简单选择排序，是一种简单直观的排序算法，能处理大部分数据。其基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次交换，得到一个按排序码从小到大排列的有序序列。

1.1 算法步骤

1. 获取序列中元素的个数，一般记为n；

2. 进行n-1次选择，即从0到n-2次选择，每次选择一个最小的数，并将这个数与数组中对应位置的值交换；

1.2 算法演示

下面给出一个简单选择排序的演示，便于理解以上的算法过程：

function selectionSort(&$arr){

    $len=count($arr);
    for($i=0;$i<$len-1;$i++){
        $min=$i;//假设$i就是最小值的位置
        for($j=$i+1;$j<$len;$j++){//让$i后面的数跟它对比
            if($arr[$j]<$arr[$min]){
                $min=$j;//更新最小数的位置
            }
        }
        if($min !=$i){//如果最小数的位置发生改变就交换两个数的位置
            $temp=$arr[$min];
            $arr[$min]=$arr[$i];
            $arr[$i]=$temp;
        }
    }
}

2. 算法分析

2.1 时间复杂度

因为要进行n次选择，每次在n-i+1（i=1,2,3…n-1）个数中选择一个最小值，

所以它的比较次数是$\sum_{i=1}^{n-1}(n-i)=\frac{n^2-n}{2}$次，移动记录的次数与序列的初始状态有关。

当序列正序时，移动记录0次；反序时，每个记录移动一次，移动次数为n-1次。因此，

总的时间复杂度为O(n^2)。由于它的常数很小，n值比较小或者文件已经按序排序时，该算法还是比较有效的。

2.2 空间复杂度

由于用到了一个临时变量，因此空间复杂度为O(1)。

2.3 算法稳定性

稳定排序算法的稳定性指的是，值相同的元素在排序后仍然保留着排序前的顺序。

简单选择排序是不稳定的算法，例如序列5 8 5 2 9，第一趟选择第一个元素2与第四个元素5交换，那么第一个5和第二个5的相对前后顺序就被破坏了。