排序算法（二）选择排序

排序逻辑：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

常见的选择排序细分为简单选择排序、树形选择排序（锦标赛排序）、堆排序。上述算法仅是简单选择排序的步骤。

 

复杂度分析：

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。

比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

 

排序过程：

初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 [38 65 97 76 49 27 49]

第二趟排序后 13 27 [65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [76 97 65 49 ]

第五趟排序后 13 27 38 49 49 [97 65 76]

第六趟排序后 13 27 38 49 49 65 [97 76]

第七趟排序后 13 27 38 49 49 65 76 [97]

最后排序结果 13 27 38 49 49 65 76 97

 

PHP 实现代码：

function select_sort($arr = array())
{
    if(empty($arr))
    {
        return FALSE;
    }

    $length = count($arr);

    for($i = 0; $i < $length - 1; $i++)
    {
        $min = $i;

        //找到最小的值
        for($j = $i+1; $j < $length; $j++)
        {
            if($arr[$min] > $arr[$j])
            {
                $min = $j;
            }
        }

        //交换位置
        $temp         = $arr[$min];
        $arr[$min]  = $arr[$i];
        $arr[$i]    = $temp;

        print_r($arr);
        echo "<br>";
    }

    return $arr;
}

$arr = array(49, 38, 65, 97, 76, 13, 27, 49);
$sort_arr = select_sort($arr);

运行结果：