理解快速排序算法过程
21/12/2021
快排通常是一中非常高效的排序算法,并且其常规实现也非常简单,往往很容易理解其思路并写出实现码,前提是需要解决递归这种思考方式。
排序思路 #
开始的时候,我们从整个数列中“任意”找出一个数作为基准数(pivot),接着拿剩余的数挨个与这个基准数比较,比它小的放在它左边,比它大的放在它右边,这便完成了一次划分(partition)。结果是我们把原来的整个数列以基准数为中点分成了两个子数列(当把子数列当成一个整体的时候,此时整个序列是有序的)。接下来要对这两个子数列做的事情和刚刚对整个数列做的事情一样…… 一直到子数列只有一个数的时候,自然成序,整个数列也在这一次次划分动作中完成排序。
再具体一点描述的话:“对整个数列施行一次划分,把小于pivot的子列看成一个新的数列,回到这句话的开头,把大于pivot的子列看成一个新的数列,回到这句话的开头”。如果大家在认真读这句话的话,你至少是读不到当前这句话的,它是读不完的。从程序的角度看,这陷入了无穷递归,最终导航到stackoverflow(.com)。从上面的描述中,我们发现是有一个结束点的,换句话说,当数列只剩一个数的时候,我们觉得划分这个动作的意义已经消失了,这时low_ptr==high_ptr。
图解快排过程 #
先给出一个待排序的数列[2, 1, 6, 4, 8, 5]。按照思路,我们需要从中找一个元素作为基准数,这里我们使用最后一个元素5作为基准数,至于为什么偏偏是最后一个元素,我们下面会结合算法性能再讨论。
实际上,我们有两个需要图解的地方,一个是快排的递归部分,一个是划分算法部分。递归部分借助划分算法不断向下进行,直到当前待划分的数列中仅剩一个元素。递归部分更像一个执行控制流,而真正的执行由划分部分完成。
下面我们用图解的方式看看划分部分是怎样实现的,我们拿上面图解中的第一步(也就是对整个原始序列进行划分那一步)来举例。
具体实现上我们借助几个变量记录索引(index)来完成比较和交换操作,prev初始为-1,这就是它在图中指向第一个元素之前的原因,它会始终记录最近一个小于pivot的值的索引;curr初始为0,也就是指向第一个元素,它会向后挨个取元素(除pivot以外),然后每拿到一个元素都会与pivot进行比较,如果小于pivot就把prev更新到这个元素处,如果大于pivot则什么也不做。
建议大家用纸笔模拟一下这个过程,结果便是划分操作的输出,随着最后一步——将pivot换到prev++的位置,pivot将数列划分成小于自己与大于自己的两个部分。
基准数(Pivot) #
基准数并没有什么最佳的选择方式,依旧取决于待排序数的数理性质,上面我们总是使用数列中最后一个元素作为基准数,实际上也可以总是使用第一个,或使用中间那个,再或者每次都随机选择一个。
使用不同的选择方式是为了算法性能,如果原来的数列是一个倒序的数列,再总是用最后一个元素作为基准数,性能会怎样?这个时候每次划分的结果总是n-1个元素和0个元素,并且每次划分的代价都是 Θ (元素数),所以此时算法运行时间的递归式为 T(n)=T(n−1)+Θ(n),解为T(n)=Θ(n2)。 这便是快排最坏情况下的时间复杂度。
理想情况下,选择的基准数总是能够将当前数列分成两等份,此时 算法运行时间递归式为 T(n)=2T(n/2)+Θ(n),解为T(n)=Θ(nlgn)。为了朝这个方向努力,应该结合待排序数列的数理性质来确定基准数的选择策略。另外,使用随机选择的方式至少可以极大程序的避免最坏情况的出现。
代码实现 #
|
|
|
|