• 👋我是Brant_zero，一名学习C/C++的在读大学生。
• 🌏️我的博客主页​​​​​​➡➡Brant_zero的主页
• 🙏🙏欢迎大家的关注，你们的关注是我创作的最大动力🙏🙏

        本篇博客学习内容是快速排序，快速排序有多种不同的版本和优化，我们这次的目的就是将这些版本都搞明白，废话不多说，我们开始。

        篇幅较长，建议配合目录来浏览。

🍂目录🍂

一、快排介绍与思想

二、hoare版本

2.1 单趟过程

2.2 多趟过程

2.3 多趟的实现

三、 挖坑法

四、 前后指针法

五、 快排的优化

5.1 三数取中选key

5.2 小区间改造

六、 快速排序改非递归版本

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。

💡单趟过程：

1.  首先记录下keyi位置，然后left和right分别从数组两端开始往中间走。
2. right先开始向中间行动，如果right处的值小于keyi处的值，则停止等待left走。
3. left开始行动，当left找到可以keyi处小的值时，left和right处的值进行交换。
4. 当两个位置相遇时，将相遇位置的值与keyi处的值进行交换，并将相遇的位置置为新的keyi。

我们来看看下面的代码，然后来分析其中容易出现的错误。

那我们一直重复这个单趟的排序，就可以实现对整个数组的排序了，这典型是一个递归分治的思想。

---

想必仍有人对hoare版本中，为什么左边置为keyi右边就要先走无法理解，这里有人就想出了一种新的快排版本，虽然算法思路一样，但是更有利于理解。

其次，这两种办法单趟走出来的结果不同，这就导致一些题目上对于快排单趟的结果不同，所以我们来理解一下这种挖坑法的算法思想。

我们先来看看下面的动画：

💡算法思路：

1. 将begin处的值放到key中，将其置为坑位(pit)，然后right开始行动找值补坑。
2. right找到比key小的值后将值放入坑位，然后将此处置为新的坑。
3. left也行动开始找值补坑，找到比key大的值将其放入坑位，置为新的坑。
4. 当left与right相遇的时候，将key放入到坑位中。
5. 然后进行[begin,piti-1],  piti,   [piti+1,end] 的递归分治。

因为有了hoare版本的实现，所以这里就不多赘述了，上面的算法思路已经将过程表述的很清楚了。

 效果检验：

---

前后指针法相比于hoare和挖坑法，不论是算法思路还是实现过程都有很大提升，也是主流的一种写法，这里我们一样来看看单趟的过程吧。

💡算法思路：

1. cur位于begin+1的位置，prev位于begin位置，keyi先存放begin处的值。
2. cur不断往前+1,直到cur >= end时停止循环。
3. 如果cur处的值小于key处的值，并且prev+1 != cur，则与prev处的值进行交换。
4. 当循环结束时，将prev处的值与keyi的值相交换，并将其置为新的keyi位置。

代码实现：

注意点：

1. 在遍历的过程中，cur是不断向前的，只是cur处的值小于keyi处的值时，才需要进行交换判断一下。
2. 在cur位置处的值小于keyi处的值时，要进行判断prev++是否等于cur，如果等于，那么会出现自己与自己交换的情况。如果相等，则不进行交换。

在实现了快速排序之后，我们发现，keyi的位置，是影响快速排序效率的重大因素。因此有人采用了三数取中的方法解决选keyi不合适的问题。

三数取中

即知道这组无序数列的首和尾后，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值(keyi)，进行快速排序，即可进一步提高快速排序的效率。

 这样，中间值的下标就被返回过来了，然后我们将这个位置换为新的keyi，就可以了。

由于快速排序是递归进行的，当递归到最后几层时，此时数组中的值其实已经接近有序，而且这段区间再递归会极大占用栈(函数栈帧开辟的地方)的空间,

接下来，我们对其进行优化，如果区间数据量小于10，我们就不进行递归快速排序了，转而使用插入排序。

我们来看看使用了小区间改造优化和三数取中优化后的快排。

💡注意点：

1. 插入排序之后两个参数，一个是数据集合的起点地址，第二个是数据量。
2. 使用插入排序时，我们要传入待排序数据集合的其实地址，即a+begin，如果传入的是a，那排序的永远都是数组a的前n个区间。
3. 插入排序传入的是数据个数，所以我们要将end-begin加上1之后才传入。快速排序中end、begin都是闭区间(即数组下标)。

因为函数栈帧是在栈(非数据结构上的栈)上开辟的，所以容易出现栈溢出的情况，为了解决这个问题，我们除了上面两种优化，还可以将快速排序改为非递归版本，这样空间的开辟就在堆上了，堆上的空间比栈要多上许多。

为了实现快速排序的非递归版本，我们要借助我们以前实现的栈，来模拟非递归。

💡实现思路：

1. 入栈一定要保证先入左再入右。
2. 取两次栈顶的元素，然后进行单趟排序。
3. 划分为[left , keyi - 1] keyi [ keyi +  1 , right ] 进行右、左入栈。
4. 循环2、3步骤直到栈为空。

效果演示：

---

总结

本篇介绍了hoare法、挖坑法、前后指针法，以及两种快排的优化方式和非递归版本，还是非常有难度的，检验大家实现的时候多看看动图，然后自己尝试写一下单趟的过程，再结合博客的内容理解快排递归的思路。这篇的内容相对硬核，光看是很难理解的，尤其是接触hoare版本和非递归版本，希望大家动手配合调试、画图来实现。

    以上就是本篇文章【快速排序(快排) (C语言实现)】的全部内容了，欢迎阅览 ！ 文章地址：http://ww.kub2b.com/news/7168.html
     栏目首页      相关文章      动态      同类文章      热门文章      网站地图      返回首页 企库往资讯移动站 http://ww.kub2b.com/mobile/ , 查看更多