Python实现常用排序

布满荆棘的人生 2022-05-29 11:17 180阅读 0赞

# **导读：** #

有人说数据结构与算法是一个程序员的内功，管你招式如何恣意潇洒，若不能伤敌就一无是处。

在《射雕英雄传》里，郭靖后来大有所作为，恐怕跟马钰偷授全真教心法存在莫大相关。而后续《神雕侠侣》中，杨过固然风采出众，“赢得青楼薄幸名”，更兼“一遇杨过误终身”的bug级别的buff。然而他与小龙女情路坎坷，后又断肠崖离别16年之久，片面解释起来：功夫不到家罢了。倘若杨过也习得《九阴真经》，或深谙《九阳神功》之道，内功修养绝非同日可语。如此这般，是李莫愁，还是金轮法王，还是痴心挖墙脚的公孙谷主，其实都成为不了二人“侠侣”路上的绊脚石。

程序员的敌人莫过于实现需求和执行效率。心中若有结构与算法，即便不能运筹帷幄、决胜于千里之外；但水来土掩、兵来将挡应该足够了。

我也是近来复习数据结构与算法，发现大一时候学的除了冒泡排序，其他忘得干净。谨防日后“失忆症”再现，细笔于此。因能力有限，错漏处望各友指教，必自省改之。

# **正文：** #

按手上大一时候的教材**《数据结构（C语言版）》（严蔚敏）**，内部排序分：插入排序，快速排序，选择排序，归并排序，基数排序。再细分如下图

![70][]

由于客观原因，只记录了我觉得常用的六个排序。并且，在接近20年的学习当中，我发现只有当所学的知识可以用自己组织的语言阐述出来的时候，才是真正的掌握了。所以，本文会基本上不会出现书本上的原语。我努力把自己所理解的东西转化成文字，以及图形，以及代码。即便“努力”，不见得就不会存在表述不清之处，希望各友加以指正。

其余待排序以及时间复杂度，待到时间宽裕后会进行补充。

（全文以python实现，皆为从小到大排序）

## 1.      插入排序 ##

**实现思想**：从第二个数值开始，设计左边区域，将待比较数在左边区域从右到左的依次比较，符合条件时，进行插入。

![70 1][]

**实现代码**：

![70 2][]

## 2.      希尔排序 ##

**实现思想**：通过设置的增量值d，将准备排序的列表分成上下结构，通过循环，实现上下相邻的两个值的比较；之后改变d值（逐渐变小），重复前面的方法，直到经历过d=1之后的排序之后，排序结束。

![70 3][]

**实现代码：**

![70 4][]

## 3.      冒泡排序 ##

**实现思想**：相邻两个数值比较，内循环结束一次，相对最大数，移置相对最右。

![70 5][]

**实现代码**：

![70 6][]

## 4.      快速排序 ##

**实现思想**：设置一个支点（一般为左边第一个数），每次循环后，大于支点的数放在支点的右边，小于支点的数放在左边，然后通过递归，传递支点左右两边的区间，重复前面步骤，直到满足条件时停止。

![70 7][]

** 实现代码：**

![70 8][]

## 5.      选择排序 ##

**实现思想**：假设最小值，并记录该数组的序号为min\_index，然后放入右边区域与待比较的数值比较，发现不是最小，则改变min\_index的值，直到离开while循环，交换假设的最小值和此时min\_index对应的值。

![70 9][]

** 实现代码：**

![70 10][]

**6.      归并排序**

**实现思想**：将一组数据拆分成长度为1的列表，相邻比较之后合并，直到合并完所有拆分出来的列表。

![70 11][]

** 实现代码：**

![70 12][]

（如果只执行函数merge\_sort（），并且打印left,right，可以看到结果如下

![70 13][]

）

![70 14][]

# 总结： #

不考虑时间复杂度，我更喜欢归并排序，因为最初实现它的人，其灵活使用递归的能耐让我折服（或许是我看的代码还太少的缘故）。然而事实上，归并排序的综合性能也是最好的，所以在处理大量复杂数值的排序上，多用用归并很不错。

如果仍有人无法理解这些排序的核心思想，我建议可以先背下来。对，就是背。想郭靖不懂什么是《九阴真经》的时候，不一样木木的背了下来吗？我们在学习过程中，有的是时间去理解，当你烂熟于心的时候，很难说不会对其中的主旨豁然开朗。即便退一步说，就算死记硬背了仍然理解不了，但是恭喜你，你至少还可以使用。

再再再再再……啰嗦一句，数据结构与算法对程序员来说真的很重要，无论考研还是找工作，都是绕不过的坎儿。所以硬着头皮上吧，自有好结果在未来等你！

[70]: /images/20220529/ce316e3bb0b84c22a652cb2a98db690a.png
[70 1]: /images/20220529/49f9f91698f444d4852e858a255e51bb.png
[70 2]: /images/20220529/eeaad82cd03d442db8fc06df90380981.png
[70 3]: /images/20220529/2beb0425990e40fdafe28ed7116cc99b.png
[70 4]: /images/20220529/470bf0714c814b89b5136e68c5e70a4a.png
[70 5]: /images/20220529/391f51afcc014e42ae3af09c971a4a5c.png
[70 6]: /images/20220529/2dd491423ac244fb9a3ab22bba4a6ff3.png
[70 7]: /images/20220529/8a73af5240f44528b392c914e583caf3.png
[70 8]: /images/20220529/d5b9006af3bd4daca92c4c7e069058fd.png
[70 9]: /images/20220529/9b7c856fbf9a416e9de0211b8657e237.png
[70 10]: /images/20220529/ecc1b39da32a4eab85630601fa1a79e5.png
[70 11]: /images/20220529/1490c62d43c143ed8110af4cfc55b287.png
[70 12]: /images/20220529/a99946bac8d3474687251895d2d0e114.png
[70 13]: /images/20220529/b3711c4d51104507b5512ffc34807b33.png
[70 14]: /images/20220529/8e0891ef3fcb4629884b56a8f0ecdc26.png