介绍
排序数组是计算机科学学科经典课程“算法和数据结构”中研究的第一个严重问题之一。在这方面，针对实习生或初级开发人员的职位，面试中经常会遇到写作排序的任务和相应的问题。
问题的提法
传统上，值得用其陈述开始介绍问题的解决方案。通常，排序任务涉及按升序对一些整数数组进行排序。但是实际上，这有点过分简单了。本节中描述的算法可用于对在其之间建立排序关系的任何对象的数组进行排序（即对于任何两个元素，我们可以说：第一个大于第二个，第二个大于第一个，或者它们相等）。您可以按升序和降序排序。我们将使用标准简化。
快速分类
上次我们讨论的是稍微复杂一点的排序-插入排序。今天，我们将讨论一种更为复杂的算法-快速排序（也称为Hoare排序）。
算法说明
快速排序算法是递归的，因此，为简单起见，该过程将输入一个数组段的边界作为输入（从包含l到不包含r）作为输入。显然，为了对整个数组进行排序，应将0作为l参数传递，将n作为r传递，按照传统，n表示数组的长度。
快速排序算法基于分区过程。分区选择数组的某些元素，然后重新排列数组部分的元素，以便将数组分为两部分：左边的部分包含小于此元素的元素，右边的部分包含大于或等于此元素的元素。该分离元件称为枢轴。
参与实施：
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
在我们的案例中，枢轴是随机选择的。该算法称为随机算法。实际上，可以通过多种方式选择枢轴：采用随机元素，或者采用该节的第一个/最后一个元素，或者以某种“智能”方式进行选择。枢纽的选择对于排序算法的最终复杂性非常重要，但稍后会更详细。分区过程的复杂度为O（n），其中n = r-1是段的长度。
现在我们使用分区来实现排序：
Partiion实现：
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
一个极端的情况-一个元素的数组具有被排序的属性。如果数组很长，那么我们使用分区，并在数组的两半上递归调用该过程。
如果您对数组1 2 2的示例进行书面排序，则会注意到它永远不会结束。为什么会发生？
在编写分区时，我们做一个假设-数组的所有元素必须唯一。否则，m的返回值将是l并且递归将永远不会结束，因为sort（l，m）将调用sort（l，l）和sort（l，m）。要解决此问题，您需要将数组分为两部分（<pivot和> =枢轴）而不是分成两部分（<pivot和=枢轴），然后对第一和第三部分调用递归排序。
分析
我建议分析此算法。
该算法的时间复杂度通过以下公式表示：T（n）= n + T（a * n）+ T（（1- a）* n）。因此，当我们调用n个元素的数组的排序时，大约需要执行n次操作来执行分区并使用a * n和（1-a）* n参数执行自身2次，因为枢轴将元素划分为分数。
在最佳情况下，a = 1/2，即，每次旋转时，枢轴将面积分成两个相等的部分。在这种情况下：T（n）= n + 2 * T（n / 2）= n + 2 *（n / 2 + 2 * T（n / 4））= n + n + 4 * T（n / 4 ）= n + n + 4 *（n / 4 + 2 * T（n / 8））= n + n + n + 8 * T（n / 8）=…。总计将是对数（n）项，因为这些项会出现直到参数减为1为止。因此，T（n）= O（n * log（n））。
在最坏的情况下，a = 1 / n，也就是说，枢轴恰好切断了一个元素。数组的第一部分包含1个元素，第二部分包含n-1。即：T（n）= n + T（1）+ T（n-1）= n + O（1）+ T（n-1） = n + O（1）+（n-1 + O（1）+ T（n-2））= O（n ^ 2）。出现正方形是由于以下事实：它出现在公式中，是对公式进行加写处理时出现的算术级数之和。
平均而言，理想情况下，应考虑各种选择的数学期望。可以证明，如果枢轴以1：9的比例对数组进行分割，则最终的渐近性将仍然是O（n * log（n））。
排序之所以称为快速排序，是因为在实践中隐藏在O号下的常数很小，这导致该算法在实践中得到广泛使用。
阅读更多
