5、排序算法

柔光的暖阳◎ 2024-03-22 21:21 17阅读 0赞

前面我们讲了[线性数据结构][Link 1]和[非线性数据解结构][Link 2]，这里我们讲一下线性数据结构上的算法——排序算法。

工作中我们实际上不用自己去写排序算法，直接调用封装好的API，比如List的Sort()方法。它们会去自动选择最优的排序算法。那么我们为什么还要学习这些算法呢？

因为通过它们，可以帮助我们建立一些基础的编程思维。比如如何平衡时间和空间复杂度，怎么更有效地利用存储空间。

除此之外，理解不同的设计思路，会让我们真切地感受到，写代码不只是单纯写写业务。虽然功能相同 ，但好的设计会带来更高的效率。这也是编程的乐趣所在。当我们想要设计好的算法时，就要综合考虑数据的各种特征，来思考是否有更多有效算法。

下面进入正题。

常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、桶排序、基数排序。

不同的排序算法有不同的适用场景，字符串的排序和数字的排序肯定还是有所区别。

下面我们的讲述都以数字为例子，不写代码，只讲思路。代码和算法的学习都可以参考[Algorithm Visualizer][]，最好自己写写练练。我一直坚信，思路有了，写代码不过是分分钟的事情。先设计、后代码，是一个好习惯。当然了，也不能死板。当没什么思路的时候，随感觉写写，或许能更快地找到解决方案。

## 冒泡排序 ##

冒泡排序的核心操作是交换。可以说它是从感觉上将数据规模缩小了。**因为交换，只需要关心两个元素。不管数据量大小，只管这两个元素的位置摆放，哪个大就把哪个放右边**。循环到不再交换为止或起终点相同为止。![7627da301cf14d4fbb0a6c64d8866971.gif][]

我们可以参考[Brute Force - Bubble Sort][]进行学习。它这里是把冒泡归到了暴力里的，说明是认为这种排序算法效率过低。

## 选择排序 ##

选择排序的重点在“**选**”上。要不就每次选**最大**的，要不就每次选**最小**的。因为每次选的都是“**最**”，所以自然而然就形成了顺序。

可以参考[Brute Force - Selection Sort][]

![b4d808285f1c49379787f423005bf231.gif][]

## 插入排序 ##

插入排序的核心点，在于“**找自己的位置**”，即未排序的元素在已排序的结果集中找自己的位置，找到自己的位置之后，就把其他元素往旁边**挤挤**，进而形成顺序。图中是把**找**和**挤**的动作放在一起了，思路没啥大的差别。

可以参考[Brute Force - Insertion Sort][]

![4eda7e5df7b14d949c6f89f2da3b6c21.gif][]

## 希尔排序 ##

希尔排序是插入排序的升级版。它通过**跳跃分组**\+**组内插排**，可以在一开始就让一些较大或较小的元素尽可能快地移到正确的位置，因为是“**跳**”着移动地，进而减少比较和交换次数。

猜测是对输入和输出的仔细观察，得到了这个优秀而有趣的排序思路。

由于动图只会展示 比较+调换位置，我这里截图说明一下**跳跃分组，**相同颜色框的为一组。这里间隔值取的是6/2=3，这是常规的间隔值取法。当间隔值为1时，就只剩下一组，走完插排即得到结果。

感觉跳跃分组也可以和前面说过的选排和冒泡等排序手法结合，都可以提升一定的效率。感兴趣的话可以测测。

![31a7f37dc3ba442fb3696cf6eaee3004.png][]

## 归并排序 ##

之前讲的几种排序，**思考逻辑**是在“线”上的。而**归并**不同，它是在**树**上的，从叶子节点开始一层一层往上合并，合并到只有一个**包含所有有序数据**的一个节点。

这里我们还是借助[Divide and Conquer - Merge Sort][] ，来理解排序地过程。注意图示中每次都将**结果集**作为操作点，要不容易看糊涂

![2cafbf0dd9e24451995a3e024bf05160.gif][]

## 快速排序 ##

如果说**归并**是通过**合并**生成树，那么**快速排序**就是通过**拆分**生成树了。它的思路是选择一个基准，然后根据左小右大的原则进行拆分。然后对拆分后的内容再用同样的方法进行拆分。最终形成了一个左小右大的树结构。

![65eb88f179fa46079bf9575c0b38a3c5.png][]

## 堆排序 ##

堆排序实际上是选择排序的一种优化。选排对待排区的操作是简单的遍历，是一种线性的操纵。而堆排则通过对待排区构建堆，完成排序。由于堆本身是一种树状结构，因而会减少一些遍历次数，进而提高效率。

这个我们可以参考 [Heap Sort Visualization][]学习，可以从动图看下堆构建的过程。

![ebf4ad12d83246afa57b942e6753d0bb.gif][]

## 桶排序 ##

桶排序和希尔排序类似，都是采用了**分组**的思想。整体上可分为两步=分组+排序。排序部分可以随意使用上边的算法。分组则又包含了建桶和放值两步。可以参考[Divide and Conquer - Bucket Sort][]：

![ecc72b60d51c4e1db92f295b623df5a1.gif][]

## 基数排序 ##

基数排序是一种取巧的桶排序方法。它主要应用于对数字和字母的排序。通过对于数字和字母本身的“权”的利用，达到排序的目的。

可以参考菜鸟教程这部分的内容学习 [1.10 基数排序 | 菜鸟教程][1.10 _ _]

## 小结 ##

到这里，常用的几种排序算法我们就说完了。我们可以看到，对于数据结构的有效利用是可以提效的。比如前面几种排序算法从思路上来讲都只用到了线性结构，而后边归并、快排等都用到了树的结构。除此之外，我们也能感受到，一个问题不止一种解法。

下一节，我们聊一下常见的算法设计思路。

##  ##

[Link 1]: https://zcywxy.blog.csdn.net/article/details/131878297
[Link 2]: https://zcywxy.blog.csdn.net/article/details/131908699
[Algorithm Visualizer]: https://algorithm-visualizer.org
[7627da301cf14d4fbb0a6c64d8866971.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1b448b38aff4481dbdbfd3c710835a20.png
[Brute Force - Bubble Sort]: https://algorithm-visualizer.org/brute-force/bubble-sort
[Brute Force - Selection Sort]: https://algorithm-visualizer.org/brute-force/selection-sort
[b4d808285f1c49379787f423005bf231.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dc0b934ac9c0494d847fbd4314d63413.png
[Brute Force - Insertion Sort]: https://algorithm-visualizer.org/brute-force/insertion-sort
[4eda7e5df7b14d949c6f89f2da3b6c21.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/47186695afec454e94bdf74dc438a9d5.png
[31a7f37dc3ba442fb3696cf6eaee3004.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bd92bfdac1e046928f5b01ee79d7dbea.png
[Divide and Conquer - Merge Sort]: https://algorithm-visualizer.org/divide-and-conquer/merge-sort
[2cafbf0dd9e24451995a3e024bf05160.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ca5fe95139c34189a6cb558c11efcf11.png
[65eb88f179fa46079bf9575c0b38a3c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/aadfc8fe23b246d29e80be052fc40ec1.png
[Heap Sort Visualization]: https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
[ebf4ad12d83246afa57b942e6753d0bb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/08524df67b664f2596b728344f04d681.png
[Divide and Conquer - Bucket Sort]: https://algorithm-visualizer.org/divide-and-conquer/bucket-sort
[ecc72b60d51c4e1db92f295b623df5a1.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/939c198d02c84a7ca0c653fbe58652f4.png
[1.10 _ _]: https://www.runoob.com/w3cnote/radix-sort.html