共计 2292 个字符，预计需要花费 6 分钟才能阅读完成。
这是咱们算法正式文章系列的最初一篇文章了，对于排序的常识咱们学习了很多，包含常见的冒泡和快排，也学习过了不太常见的简略插入和希尔排序。既然明天这是最初一篇文章，也是排序相干的最初一篇，那咱们就来轻松一些，再来学习两个非常简单的排序算法。
简略抉择排序
首先是简略抉择排序，它划分在了抉择类排序上面，不过其实也能够看成是替换类的排序。因为它的外围代码中也是有替换操作的实现的。对于这个排序没有什么太多好说的，每次在遍历中找出最大或者最小的数据，而后将它放到相应的地位就能够了。咱们先来看代码，而后再看图示的解析。
function SelectSort($numbers){$n = count($numbers);
for($i = 0 ; $i < $n ; $i++){
$k = $i;
for($j = $i+1 ; $j < $n ; $j++){if($numbers[$j] < $numbers[$k]){$k = $j;}
}
if($k != $i){list($numbers[$i], $numbers[$k]) = [$numbers[$k], $numbers[$i]];
}
}
echo implode(',', $numbers), PHP_EOL;
}
SelectSort($numbers);
// 13, 27, 38, 49, 49, 65, 76, 97代码不简单吧，能够留神到它也有替换代码的呈现。咱们应用的是上篇文章中的小彩蛋中的替换形式进行的数据地位的替换。它和冒泡以及快排那种专门的替换型排序算法还是有些许不同的，每次替换的 i 这个地位是不变的，什么意思呢？比方咱们当初的 i 是 0，也就是说整个序列中最小的数据应该是要放在这个中央的。所以 j 循环是从 i + 1 的地位开始循环的，而后不停地和 i 这个地位的数据进行比拟，并一直地更新 k（k 在一开始是指定为 i 的）。找到最小的数据之后间接将这个数据和 i 的数据交换，这样最小的数据就放到了 i 的地位上了。这就是简略抉择排序的核心思想。
这一大段说起来可能会看得比拟懵圈。还是看看图吧！
咱们仍然还是以第一趟的具体过程为例。
- k = i，而后 j 从第二个数据开始遍历
- 如果发现 numbers[j] 小于 numbers[k] 的数据，也就是更小的数据，就让 k = j
- j 循环遍历实现后，k 指向的下标就是最小那个数据，于是替换 k 和 i 的值
- 一趟排序下来，最小的数据就放到了最后面的地位了
是不是感觉和冒泡有点像呀？的确是很像，冒泡也是一趟外层循环就能够把某个最大或者最小的值放到正确的地位上。不过须要留神的是，冒泡是前后两个数据相比，很有可能每次比拟都会产生替换。而抉择排序则是以一个下标指针的地位挪动来确定数据，最初也只进行一次替换。所以说，它是有选择性的替换，而不是纯正的一路替换到底。
简略桶排序
真正的桶排序还是比较复杂的，但明天咱们学习的这个简略的桶排序则是真的简略的不行。它体现的是一种以空间换工夫的形式，具体是怎么换的呢？
function BucketSort($numbers){$bucketList = [];
$maxValue = max($numbers);
for($i=0;$i <= $maxValue;$i++){$bucketList[$i] = 0;
}
foreach($numbers as $n){$bucketList[$n]++;
}
$sortList = [];
foreach($bucketList as $k => $v){if($v > 0){for( ; $v > 0 ; $v--){$sortList[] = $k;
}
}
}
echo implode(',', $sortList), PHP_EOL;
}如果是针对的数字类型的排序操作，特地是这个数字基数不大，比如说是类型枚举之类的数据，咱们都能够应用这种桶排序的形式。首先咱们要看以后最大的数字是几，而后初始化一个数组到这个最大数字的下标，并将所有内容设置为 0。接着遍历原始的排序数组，给这个要排序数据对应的值加 1。于是，待排序序列所代表的那些键的值都会变成 1，同时，如果有雷同的数据，咱们应用的是 ++ 操作，这个数据对应的键值就会持续加 1。具体的过程就如下图所示：
置信这个图曾经阐明得十分清晰了吧，也不须要咱们再深刻地解释了吧。这就是这种最简略的桶排序形式，咱们也能够将这个桶数组的内容换成二维数据，这样咱们就能够实现更简单数据的排序操作了。不过还是要留神，肯定是针对数字类型的哦。咱们介绍的这种桶排序其实是真正的桶排序的一种变体，也有人叫它为“计数排序”。
真正更加齐备一些的桶排序其实是先将数据分成不同的组，每个组能够看成是一个桶。而后在这个桶内将组内的数据排序，排序实现之后再将这些组（桶）连接起来。它的工夫复杂度是靠近于 O(n) 的。不过就像咱们介绍的这个最简略的桶排序一样，简单的桶排序也是有许多严苛的要求的，所以尽管它的成果很高，但却并不常见。
总结
明天的内容非常简单吧，简略抉择其实也是一种替换排序，但它在大类中还是划归到了抉择排序这个类型中。而桶排序是属于基数排序的一种。各种排序其实还有很多，但除了咱们学习的这些之外，其它的都会更加的简单也并不常见，大家有趣味的能够在下期咱们的总结文章中理解到有哪些能够持续深刻学习的内容。精彩还在持续，不要错过哦！
测试代码：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7. 排序 /source/7.3 其它排序：简略抉择、桶排序.php
参考文档：
《数据结构》第二版，严蔚敏
《数据结构》第二版，陈越
《啊哈！算法》
===========
各自媒体平台均可搜寻【硬核项目经理】