数据结构——排序（4）

作者：几冬雪来

时间：2023年4月12日

内容：数据结构排序内容讲解

目录

前言： 

1.快速排序中的递归：

2.小区间优化： 

3.递归改非递归： 

4.归并排序： 

5.归并排序的非递归形式（框架）： 

结尾： 

---

前言： 

在前一篇博客中我们对快速排序的代码进行了一步优化，将它优化出来了3种方法——随机找key法，三数取中法和前后指针法。而在今天，我们则在已经优化过的基础上，对我们的代码进行进一步的优化。 

1.快速排序中的递归：

在我们之前书写快速排序的时候，每次都是先写一趟快速排序，而后再使用递归的方法让我们的数组通过几次快速排序后一步步变得有序。而我们的这个递归的行为则类似我们的二叉树的操作，越往下走递归的次数越多。 

而在我们二叉树的那个板块曾经就有说明过，当我们递归次数很多的时候，最后一层的递归出来的结果个数是我们总数的一半，往上到倒数第二层是1/4，再然后是1/8。

那么在这里就有人提了一个建议，就是在我们快速排序排到最后倒数第4层的时候我们就不再继续往下递归下去了，之后无序的数组我们用直接插入排序来将其变得有序，这样子做就可以大大的减少我们的递归的次数。

这种方法就被我叫做——小区间优化。 

2.小区间优化： 

最小区间法，顾名思义就是当我们的区间变得较小的时候，这里用其他的排序来代替我们的快速排序。那么在这里，我们就将它们的代码写出来。

这里就是我们的小区间优化法，在这里我们有需要小心的地方，也存在着我们可以普及的内容，接下来我们就来一一细说一下。 

在这里我们的元素的个数是可以进行修改的。这里的大于10也可以修改为大于20或者是50，但是如果在这里进行了修改的话，我们的小区间优化法可能会适得其反。

这里要注意的是，如果区间个数过多，可能会导致这里小区间优化法的运行时间比没有小区间优化法的时间要长。且原数组元素个数少的话，小区间优化法的优化程度及其有限，当原数组的元素个数多的时候，小区间优化法才能更好的表现出来它的优势。

但是在这里我们不单单是讲小区间优化法的问题，我们是要依靠它来引出一个新的问题。

3.递归改非递归： 

因为我们的快速排序所运用的方法是递归，所以这里就牵扯出来一个经典的问题——栈溢出。当我们的递归次数过多的时候，哪怕我们的代码是对的，但是它在debug中依旧也是跑不起来。栈的内存满了，我们的代码也会调试不起来，因此针对程序员而言，如果某个程序的递归没问题我们就不需要管它，相反如果出现问题的话，我们要学会将我们的递归改为非递归。

而在这里我们用到的知识则是栈板块的知识。 

首先我们要把栈的头文件和.c文件一起复制到我们当前文件中。接下来就要开始我们非递归的操作了。这里要用循环来代替我们的递归，第一个要想到的是，在递归中我们递归的是什么东西，而在快排当中我们递归的对象是区间（对象不是数组因为数组不在栈中）。 因此我们的栈也要存区间。

这就是我们非递归形式的快速排序的操作过程，第一次先将0和9存放到栈中，然后将其取出，找到我们的key后将其分为左右区间，接下来再把6和9先存放到栈中，而后存放0和4，下来我们继续以上的操作，直到最后我们的区间只剩下一个值或者不存在就结束。 

知道这些操作之后下来就是书写我们的代码了。 

这就是我们的代码和它的讲解了，虽然这里我们的代码从递归形式改为非递归形式，但是实际上它的效率并没有什么提升，非递归形式只是防止栈溢出罢了。 

4.归并排序： 

接下来要讲解的排序是我们的归并排序，归并排序也是我们一种十分有效的排序方法。 

接下来是我们归并排序的操作图。 

在这里我们将我们的数组拆为平均两个部分，然后判断两个部分是否有序，无序的话就继续往下拆分，直到我们拆分下最后一个数的时候，这里我们就开始回归，回归的时候我们的每个区间都会变得有序。 

当最后我们合并剩下两个区间的时候，我们最后再把它们进行一次合并排序，最后我们的数组就可以变得有序起来了。 

同样的在这里我们的归并排序的时间复杂度也为标准的O(N*logN)。因为在这里我们每层需要排序的个数都为N，并且每次排序都是将区间平均的一分为二，所以它的时间复杂度是logN。 

在归并排序中有人看我们的这个图片，以为每次分解都要建立一个小数组，但是其实不是的。

在这里我们只需要一个临时数组来帮助我们进行排序，每次排序之后我们就要将我们的内容给拷贝出去。当最后归并到我们的左右都有序之后，将它拷贝回原数组中，它就有序了。接下来就是来书写我们的代码了和其解析。 

这就是我们的代码和它的解析了，这里需要注意的是，在这里我们每次递归都是要用到整个数组的元素，因此在判断那里我们需要用到等于号。 

这里我们用的数组刚刚好可以被我们平均的拆分为2个大小相等的数组，如果这里数组中元素的个数是单数的话，我们的代码依旧可以跑起来吗？ 

这里从结果中可以看出，哪怕我们的数组元素的个数是单数的，我们依旧可以通过这种方法对我们的数组进行排序，它并不影响我们排序的进行。 

5.归并排序的非递归形式（框架）： 

同样的在这里，我们的归并排序也有它的非递归形式。在前面我们讲到，递归变循环我们又两种方法，一种的借助栈来进行修改，另外一种则是直接修改，而在这里归并排序的非递归形式是自己对其进行修改。

这里我们又一个方法。

在这里我们取一个gap值，每次归并后我们的gap值增加，我们每次参与归并的元素个数也随之增加。 就类似我们上图这样，不过这种方法有需要修改的点，比如边界问题等，我们就留到下一篇博客来讲解了。

接下来我们就来浅浅的写一写我们的代码和它的解析。 

这就是我们归并排序非递归形式代码的一个大体的框架，这其中还存在着很多的问题。这些我们就留到下一篇博客再来讲解吧。 

结尾： 

到这里我们的数据结构的内容就再一次的讲解完毕了，很快的我们的数据结构排序板块的内容就要结束了，后面我们还要对我们的归并排序的非递归形式进行优化。最后希望这篇博客能为大家带来一点的帮助。