这是我们官方算法系列文章的最后一篇。我们学习了很多关于排序的知识，包括常见的冒泡和快速排序，也学习了不太常见的简单插入和希尔排序。由于这是今天的最后一篇文章，也是最后一篇与排序有关的文章，所以我们不紧不慢地学习两个非常简单的排序算法。简单选择排序首先是简单选择排序，属于选择排序之下，但也可以看作是交换类的排序。因为它的核心代码也有交换操作的实现。这个排序就不多说了，每次遍历找到最大或者最小的数据，然后放到相应的位置即可。我们先看代码，再看图的分析。函数SelectSort($numbers){$n=count($numbers);对于($i=0;$i<$n;$i++){$k=$i;for($j=$i+1;$j<$n;$j++){如果($numbers[$j]<$numbers[$k]){$k=$j;}}if($k!=$i){列表($numbers[$i],$numbers[$k])=[$numbers[$k],$numbers[$i]];}}echoimplode(',',$numbers),PHP_EOL;}SelectSort($numbers);//13,27,38,49,49,65,76,97代码并不复杂，你可以注意到他们也有兑换码。我们使用上一篇彩蛋中的exchange方法来交换数据位置。与冒泡、快速排序等特殊的交换排序算法略有不同。i在每次交换中的位置不变。这是什么意思？比如我们当前的i是0，也就是说整个序列中最小的数据应该放在这个地方。因此第j次循环从i+1位置开始，然后不断的和i位置的数据进行比较，不断更新k（k一开始指定为i）。找到最小的数据后，直接和i的数据交换这个数据，使得最小的数据放在i的位置。这就是简单选择排序的核心思想。这一段听起来可能令人困惑。或者看图！我们还是以第一次旅行的详细过程为例。k=i，然后j从第二个数据开始遍历。如果发现numbers[j]小于numbers[k]，也就是数据更小，让k=jj循环遍历完成后，k指向的下标就是最小的数据，所以取值k和i交换排序，最小的数据放在最前面。是不是有点冒泡的感觉？确实很像，冒泡也是跑外层循环把某个最大值或者最小值放在正确的位置。但是需要注意的是，冒泡是前后两个数据的对比，很有可能每次对比都会发生一次交换。选择排序是通过移动一个下标指针的位置来确定数据，最后只进行一次交换。因此，它是一种选择性的交换，而不是一路到最后的纯交换。简单桶排序真正的桶排序还是比较复杂的，但是我们今天学习的简单桶排序真的很简单。它体现了一种以空间换取时间的方式，具体是如何交换的呢？函数BucketSort($numbers){$bucketList=[];$maxValue=max($numbers);对于($i=0;$i<=$maxValue;$i++){$bucketList[$i]=0;}foreach($numbersas$n){$bucketList[$n]++;}$sortList=[];foreach($bucketListas$k=>$v){if($v>0){for(;$v>0;$v--){$sortList[]=$k;}}}echoimplode(',',$sortList),PHP_EOL;}如果是对数值类型的排序操作，尤其是数字基数不多，比如对于类型枚举这样的数据，我们都可以用这个桶排序方法。首先我们要看当前最大的数是多少，然后初始化一个数组为最大数的下标，并全部置0。然后遍历原排好序的数组，给最大数对应的值加1要排序的数据。因此，待排序的序列所代表的key的值都会变成1。同时，如果有相同的数据，我们使用++操作，这个数据对应的key值会继续增加1。具体过程如下图所示：相信这张图已经解释的很清楚了，我们就不用再深入解释了。这是最简单的桶排序方法。我们也可以把这个桶数组的内容换成二维数据，这样我们就可以实现更复杂的数据排序操作。但需要注意的是，必须为数字类型。我们介绍的桶排序其实是真正的桶排序的变种，也有人称之为“计数排序”。比较完整的桶排序其实就是先把数据分成不同的组，每个组都可以看成是一个桶。然后把这个桶里面组里的数据排序，排序完成之后再把这些组（桶）连接起来。它的时间复杂度接近于O(n)。但是，就像我们介绍的最简单的桶排序一样，复杂的桶排序也有很多严格的要求，所以虽然效果很高，但是并不常见。总结今天的内容很简单。简单选择其实就是交换排序的一种，只是在一般的范畴里还是属于选择排序的类型。桶排序是基数排序的一种。其实排序有很多种，但是除了我们学过的，其他的会比较复杂，不常见。如果大家有兴趣，可以在我们下一期的总结文章中了解到可以深入研究的内容。.精彩还在继续，千万不要错过！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7。排序/source/7.3其他排序：simpleselection,bucketsorting.php参考文档：《数据结构》第二版，颜伟民，第二版，陈越《啊哈！算法》==========各媒体平台可以被搜[硬核项目经理]
