大家好！我是小米，一个29岁，积极活泼、喜欢分享技术的程序员。今天我们来聊聊快速排序（QuickSort），一个经典的排序算法，也是许多面试中的常客！

快速排序的基本思想

快速排序（QuickSort）是一种基于分治思想的排序算法。它通过选取一个“基准元素”将待排序数组划分为左右两个部分，分别对左右部分递归地进行快速排序，最终实现数组的有序化。

简单来说：

1. 选取基准元素；
2. 将比基准元素小的元素放在它的左边，比它大的放在右边；
3. 递归地对左右两个子数组进行快排。

这个算法的时间复杂度是O(n log n)，在最坏情况下（例如输入数组已经有序的情况下）会退化为O(n^2)，但它的平均时间复杂度仍然是O(n log n)，因此在实际应用中，快排非常高效。

快速排序的实现

现在，咱们直接上代码！我会逐步讲解如何手写一个快速排序。

代码讲解

这段代码实现了一个简单的手写快速排序。让我们逐步解析一下代码的逻辑：

• quickSort(): 这是主函数。它接收三个参数：要排序的数组arr，数组的左边界left和右边界right。在这个函数中，通过partition()方法将数组分为两部分，并递归地对这两部分进行快速排序。
• partition(): 这是快排的核心。它的作用是选择一个基准元素（这里我们选择了最右边的元素），并通过一轮遍历将小于基准的元素放在左边，大于基准的放在右边，最终将基准元素放到正确的位置。返回值是基准元素的索引。
• swap(): 一个简单的辅助方法，用来交换数组中的两个元素。在partition()过程中，我们需要频繁地交换元素，这个方法让代码更清晰。

为什么选择递归？

递归的核心思想就是“拆分”。我们把问题拆解成更小的子问题，并且这些子问题和原问题结构类似，只是规模小了很多。最终，当子问题变得足够小，我们就可以直接解决它们。

在快排中，每次递归都把数组拆成了两部分，分别递归处理它们。由于每次递归都处理一部分数组，最终我们就能让整个数组有序。

复杂度分析

快速排序的时间复杂度取决于基准元素的选择：

平均情况：每次都能把数组大致分成两个相等的部分。此时，时间复杂度为O(n log n)。

最坏情况：基准元素每次都把数组分成两个极端（一个部分为空，另一个部分包含所有元素），此时时间复杂度为O(n^2)。

为避免最坏情况，我们可以随机选择基准元素，或者使用“三数取中法”（选择左、中、右三个元素的中位数作为基准）。

随机选择基准元素

为了提高快排的效率，我们可以随机选择基准元素，从而减少最坏情况发生的概率。我们可以对partition()进行改进，添加随机选择基准元素的逻辑：

改进后的快速排序

在这个改进版的快排中，我们添加了一个随机选取基准元素的功能。通过随机选取基准元素，避免了在某些特殊情况下（如输入数组已经有序的情况）导致最坏时间复杂度的发生。

这样，即使面对极端的输入数据，我们也能获得平均情况下的时间复杂度O(n log n)，提高了快排的稳定性和效率。

END

快速排序是排序算法中的经典之作，其高效的性能使得它在各种场合中都得到了广泛的应用。今天，我们一起手写了快排，并且学习了如何通过随机化基准元素来优化它的性能。

希望这篇文章对你有所帮助！有任何问题或想要深入讨论的内容，欢迎在评论区留言交流！更多实战算法内容，敬请关注小米的后续分享！

小米小贴士：保持好奇心，不断练习，算法其实并没有那么难哦！

我是小米，一个喜欢分享技术的29岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！