钛节点

排序篇之选择排序

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

你王老师始终是你王老师，你自以为期中考试你的答辩题目弄成《论冒泡排序在社会主义建设中的贡献与作用》就可以拿到A+级了，然并卵，王老师还是仅仅给了你一个C及格级。

毕竟，王老师那是见得多了，区区冒泡就敢来装高端搞大新闻？回家再修炼两年吧。

![](https://ti-node.com/static/upload/6401402899972227073)

选择排序相对来说是一种思路比较简单粗暴明了清晰的排序算法，主题思路就是：从一坨数字中找出最小的放到第一位，然后从剩余数字中再找最小的放到第二位，依次继续，知道排序完毕。

这不是特么废话么，哪个排序算法不是这么干的？
- 首先，我们定义一个基准数A，并假装TA暂时就是最小的那个（一般情况自己不作死的话，就选第一个），定义一个变量min_index并将A的数组索引位置赋值给min_index
- 然后，我们将min_index索引位置上的数字（第一轮其实就是A）依次（开始内循环）和剩余其他所有数字比较大小，如果基准数比某数字大了，那么（注意了⚠️⚠️⚠️）我们将某数字所在的数组索引位置赋值给min_index
- 然后，现在最小值俨然已经发生了变化，然后循环继续重复前两个步骤一直到本轮终止结束

不管你能不能看得懂我画的啥意思，反正我强烈你一定要画一画，纸笔演练：
![](https://ti-node.com/static/upload/6401433562721026048)

```php
<?php
$arr = [ 6, 4, 7, 2, 9, 8, 1 ];
$length = count( $arr );
// 这里值得注意下，outer的最大值不能超过length-1而不是length，因为如果最后一个数字就剩最后一个了，不需要再拿出来判断大小
for( $outer = 0; $outer < $length - 1; $outer++ ){
  // 先选择6为基准数字和基准位置
  $min_index = $outer;
  // 和后面的数字依次进行比较，这里值得注意的inner的最大值上限是length，而不能是length-1，仔细思考一下
  for( $inner = $outer + 1; $inner < $length; $inner++ ){
    // 如果最小基准位上的数比后面的数字大，那么，将后面数字的数组索引赋值给min_index
    if( $arr[ $min_index ] > $arr[ $inner ] ){
	  $min_index = $inner;
	}
	// 等所有内循环跑完毕后，判断最小数字的索引位置和 outer 是否相同，如果相同，说明outer位置上数就是最小的
	// 如果不一样，那么，min_index和outer两个位置的数字
	if( $min_index != $outer ){
	  $temp = $arr[ $outer ];
	  $arr[ $outer ] = $arr[ $min_index ];
	  $arr[ $min_index ] = $temp;
	}
  }
}
print_r( $arr );
```

那么，话说回来，这个排序算法为啥就比冒泡排序屌呢？***这里先卖个关子，最后总结的时候出个汇总***。现在就临时用下面的代码做个简单的测试吧：
```php
<?php
function bubble( $arr ){
  $length = count( $arr );
  $flag = true;
  for( $outer = 0; $outer < $length && $flag; $outer++ ){
    $flag = false;
    for( $inner = $length - 1; $inner > $outer; $inner-- ){
      if( $arr[ $inner ] < $arr[ $inner - 1 ] ){
        $temp = $arr[ $inner ];
        $arr[ $inner ] = $arr[ $inner - 1 ];
        $arr[ $inner - 1 ] = $temp;
        $flag = true;
      }   
    }   
  }
  return $arr;
}
function select( $arr ){
  $length = count( $arr );
  for( $outer = 0; $outer < $length - 1; $outer++ ){
    $min_index = $outer;
    for( $inner = $outer + 1; $inner < $length; $inner++ ){
      if( $arr[ $min_index ] > $arr[ $inner ] ){
        $min_index = $inner;
      }   
    }   
    if( $min_index != $outer ){
      $temp = $arr[ $outer ];
      $arr[ $outer ] = $arr[ $min_index ];
      $arr[ $min_index ] = $temp;
    }   
  }
  return $arr;
}
$length = 200;
for( $i = 0; $i < $length; $i++ ){
  $arr[] = mt_rand( 1,1000);
}
// 冒泡算法
$begin = microtime( true );
for( $i = 0; $i < $length; $i++ ){
  bubble( $arr );
}
$end = microtime( true );
echo PHP_EOL.PHP_EOL.PHP_EOL."冒泡算法耗费时间：".( $end - $begin ).PHP_EOL;
// 选择算法
$begin = microtime( true );
for( $i = 0; $i < $length; $i++ ){
  select( $arr );
}
$end = microtime( true );
echo "选择算法耗费时间：".( $end - $begin ).PHP_EOL.PHP_EOL.PHP_EOL;
```
运行结果如下图所示：

![](https://ti-node.com/static/upload/6401429588672512001)

200条数据，就能差出一半时间来，吓人不？王老师终究是你王老师，嫩还是嫩了点儿的。

------