快速排序算法要点、流程及示意图

terry 2年前 (2023-09-27) 阅读数 63 #数据结构与算法

快速排序

快速排序是由 C.A.R. 提出的。Hoare于1962年改进了冒泡排序。基本思想是：通过一次排序将待排序的数据分成两个独立的部分，其中一个部分中的所有值都小于另一部分中的所有值，然后快速将两个部分分别排序。。所有的过程都可以递归地继续下去，最终所有的数据都成为一个有序的序列。

例如要排序的数组是a[0],a[1],...a[n-1]，快速排序步骤为：

快速排序每一遍的核心工作是：选择一个元素作为基数，然后将所有小于它前面的数字放入其中，并将所有比它前面的数字大的数字放入其中。

假设下面有8个元素，分别是59,25,71,16,62,84,34,45，现在已经快速排序了。

初始化变量i=1，j=7，并以第一个元素a[0]为基数，然后从i开始返回第一个大于a[0]的元素，59对比25，

由于 25 小于 59，所以退后一步继续比较，

71 大于 59，找到第一个大于 59 的元素。然后从 j 开始向前追溯，找到第一个小于 59 的元素。基数。比较59和45，45小于59，所以我们找到第一个小于基数的元素。

这次交换a[i] 把a[j]的值交换一下，分别是71和45，你发现交换的效果了吗？这就是把大的推在后面，把小的推在前面。

继续寻找下一个大于基数的元素，将i后移一步，16小于59，

i后退一步，现在62大于59，元素更大。共找到 59 个。然后j期待找到基数的第一个较小的元素。

34小于59，所以我们要找的元素找到了。

此时a[i]和a[j]的值发生变化，即62和34颠倒过来，

继续寻找下一个大于基数i的元素前后移动一步，距离59又多了84，找到，

和j向前查找，发现已经和i重叠了，所以停止向前比较。

立即将重叠位置上一个元素的值替换为基本数，即替换a[j-1]和a[0]的值，即把34换成59。此时，第一个快速排序完成。

接下来，快速准备第二遍。第一遍执行完毕后，引用编号将序列分为两个分区，要排序的对象是最后一个引用编号之前的元素，也就是 59 之前的元素。

对于这个序列，开头 i= 0，j=3，本次行程的参考号a[0]为34。然后从i开始向后查找第一个大于[0]的元素。与前 25 个相比，增加了 34 个。

由于25小于34，我们退一步继续比较。此时45大于34，我们找到第一个元素。对于大于基数的元素，

然后出现 j，并继续查找小于基数的第一个元素。 16 小于 34，这就是您要查找的元素。

此时a[i]和a[j]的值改变了，即45和16改变了。

继续查找下一个大于基数的元素。将i前后移动一步，找到已经与j重叠的那一个。，再次停止比较，

立即替换前一个与参考数重叠位置的元素的值，即替换a[j-1]和a[0]的值，即把34交换成16. 至此，第二个快速序列结束。

接下来，准备快速序列的第三遍。基数 34 将序列分为两个分区并继续处理前一个分区。

此时分区序列只有16和25两个元素。初始i=1，j=1，基数a[0]为16。i和j一开始重叠。此时，找到了大于基数的元素，但是j没有找到小于基数的元素，所以没有变化。

接下来，快速连续准备第四遍。第一遍执行后，会先处理59之前的分区，现在处理59之后的分区。该处理顺序由递归处理确定。

对于后续的划分，初始i=6，j=7，以序列的第一个元素为基数，即84。然后从i开始向后查找大于基数的第一个元素A。首先将 84 与 62 进行比较。

由于 62 小于 84，我们后退一步到达序列的末尾。此时71小于84，无法找到大于基数的元素。然后j向前查找基数最小的元素，71小于84，找到该元素。

然后用基数 84 替换 71 以完成第四个快速序列。

接下来，快速连续准备第五遍。参考号84只有前一个分区，下一个分区将继续处理。

此时划分序列只有两个元素71和62。一开始i=6，j=6，基本数为71。i和j一开始重合。此时i找不到大于参考数的元素，j则找到小于参考数的元素。

因此 71 和 62 被交换以完成第五个快速序列。至此，整个序列就排序完成了。

作者：超人王小健
链接：https://juejin.im/post/5bd65581e51d454c410e5df0
来源：掘金商业转载请联系作者授权。非商业转载请注明出处。

本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。