【JavaScript快速排序算法】差别版本原理分析

源代码 · 2024-10-5 16:28:44

分析

快速排序（QuickSort），又称分区交换排序（partition-exchange sort），简称快排。快排是一种通过基准分别区块，再不停交换左右项的排序方式，其接纳了分治法，淘汰了交换的次数。它的基本头脑是：通过一趟排序将要排序的数据分割成独立的两部门，此中一部门的所有数据都比另外一部门的所有数据都要小，然后再按此方法对这两部门数据分别进行快速排序，整个排序过程可以递归或迭代进行，以此让整个数列变成有序序列。
实现过程

在待排序区间找到一个基准点(pivot)，便于明白一般是位于数组中央的那一项。
逐个循环数组将小于基准的项放左侧，将大于基准的项放在右侧。一般通过交换的方式来实现。
将基准点左侧全部项和基点右侧全部项分别通过递归(或迭代)方式重复第1项，直到所有数组都交换完成。

表示图

表明：以某个数字为基点，这里取最右侧的数字8，以基点分别为两个区间，将小于8的数字放在左侧区间，将大于8的数字放在右侧区间。再将左侧区间和右侧区间分别放到递归，按照最右侧为基点，继续分解。直到分解完毕，排序完成。这是此中一种常见的分区递归法，除了这种方式外，还有其他实现方式。
性能分析

均匀时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的差别而差别，可以检察差别版本的源码
代码

快排方式1, 新建数组递归版本。无需交换，每个分区都是新数组，数目巨大。

这个版本使用了JS数组可变且随意拼接的特性，让每个分区都是一个新数组，从而无需交换数组项。
这个方式非常简朴易懂，但理论上来讲不是完全意义上的快排，服从较差。

【JavaScript快速排序算法】差别版本原理分析

所属分类: 问答交流

新帖推荐: 30日

推荐作品