选择排序

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

1. 算法描述

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

• 初始状态将待排序分为有序区和无序区，有序区在前，且为空；
• 从待排序的数列中挑出一个元素（默认为第一个），假设为最小值，记录它的下标；
• 遍历剩余数列，如果找到比上一步中的“最小值”还小的数，则将最小值的下标改为当前值的下标，继续遍历直到结束，将“最小值”下标标记的数放入有序数列；
• 重复前两步，直到n-1趟结束，这时数列就有序化了。

2. 动图演示

image

3. 代码实现

实现方式一为普通方式；方式二为改进版，方式一中的一次遍历，只是找出最小值，而方式二则是在一次遍历中同时找出最小值和最大值。我本以为改进后效率会提升一倍，但是结果并没有，只是遍历的次数减少了一半，我也不知道为什么，请知道的小伙伴儿能不吝赐教，在下将感激不尽。

<?php
//输出数组
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

//检测数组
function check_arr($arr){
    if(!is_array($arr)){
        return 'arr error';
    }

    $len = count($arr);
    if($len <= 1){
        return $arr;
    }

    return true;
}

//计算耗时
function time_consuming($start, $end, $name=''){
    $t = $end - $start;
    var_dump($name.'耗时：'.$t);
}

//显示起始时间
function show_time($start, $end, $name=''){
    var_dump($name.' start：'.$start);
    var_dump($name.' end  ：'.$end);
}

//获取乱序的数组
function get_test_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = mt_rand( 1,1000);
    }

    return $arr;
}

//获取顺序的数组
function get_sort_arr($len = 200){
    for( $i = 0; $i < $len; $i++ ){
      $arr[] = $i;
    }

    return $arr;
}

//排序主程序
function selection_sort($arr){
    $check_re = check_arr($arr);

    if($check_re === true){
        selection_sort1($arr);
        selection_sort2($arr);
    }else{
        echo 'error';
        var_dump($arr);
    }
}

$arr = get_test_arr();
// $arr = get_sort_arr();
// echo_arr($arr);
selection_sort($arr);

//排序方式一
function selection_sort1($arr){
    $len = count($arr);
    $start = microtime(true);

    //统计内循环的执行次数
    $tt = 0;
    for ($i=0; $i < $len-1; $i++) {
        $min_index = $i;
        for ($j=$i+1; $j < $len; $j++) { 
            // var_dump($arr[$min_index].'+'.$arr[$j]);
            if($arr[$j] < $arr[$min_index]){
                $min_index = $j;
            }
            // echo_arr($arr);
            $tt++;
        }

        if($i != $min_index){
            $tmp = $arr[$i];
            $arr[$i] = $arr[$min_index];
            $arr[$min_index] = $tmp;
        }
    }

    var_dump($tt);
    $end = microtime(true);
    time_consuming($start, $end, 'selection_sort-1');
    // echo_arr($arr);
}

//排序方式二
function selection_sort2($arr){
    $len = count($arr);
    $start = microtime(true);

    //统计内循环的执行次数
    $tt = 0;
    //计算外循环的执行次数
    $times = floor($len/2);
    for ($i=0; $i < $times; $i++) {
        $mix = $i;
        $max = $len-1-$i;

        if($arr[$max] < $arr[$mix]){
            // var_dump('swap mix-max: '.$arr[$mix].'-'.$arr[$max]);
            $tmp = $arr[$max];
            $arr[$max] = $arr[$mix];
            $arr[$mix] = $tmp;
        }

        for ($j=$i+1; $j < $len-1-$i; $j++) { 
            // var_dump('number: '.$arr[$mix].'+'.$arr[$max].'+'.$arr[$j]);
            if($arr[$j] < $arr[$mix]){
                $mix = $j;
                continue;
            }

            if($arr[$j] > $arr[$max]){
                $max = $j;
            }
            // echo_arr($arr);
            $tt++;
        }

        if($mix != $i){
            // var_dump('swap mix: '.$arr[$mix].'-'.$arr[$i]);
            $tmp = $arr[$i];
            $arr[$i] = $arr[$mix];
            $arr[$mix] = $tmp;
        }

        if($max != $len-1-$i){
            // var_dump('swap max: '.$arr[$max].'-'.$arr[$len-1-$i]);
            $tmp = $arr[$max];
            $arr[$max] = $arr[$len-1-$i];
            $arr[$len-1-$i] = $tmp;
        }

        // echo_arr($arr, '-');
    }

    var_dump($tt);
    $end = microtime(true);
    time_consuming($start, $end, 'selection_sort-2');
    // echo_arr($arr);
}

image.png