快速排序算法快速排序算法|算法设计与分析

本文概述

算法
分割算法

它是分而治之类型的算法。
除法：重新排列元素并将数组拆分为两个子数组, 并在两次搜索之间的一个元素中, 左子数组中的每个元素小于或等于平均元素, 右子数组中的每个元素大于中间元素。
征服：递归地, 对两个子数组进行排序。
合并：合并已排序的数组。
算法

QUICKSORT (array A, int m, int n) 1 if (n > m) 2 then 3 i ← a random index from [m, n] 4 swap A [i] with A[m] 5 o ← PARTITION (A, m, n) 6 QUICKSORT (A, m, o - 1) 7 QUICKSORT (A, o + 1, n)

分割算法分区算法在一个位置重新排列子数组。

PARTITION (array A, int m, int n) 1 x ← A[m] 2 o ← m 3 for p ← m + 1 to n 4 do if (A[p] < x) 5 then o ← o + 1 6 swap A[o] with A[p] 7 swap A[m] with A[o] 8 return o

图：显示执行跟踪分区算法

文章图片
快速排序示例：

44 33 11 55 77 90 40 60 99 22 88

设44为Pivot元素, 并从右向左进行扫描
将44与右侧元素进行比较, 如果右侧元素小于44, 则将其交换。因为22小于44, 所以交换它们。

22 33 11 55 77 90 40 60 99 44 88

现在将44与左侧元素进行比较, 并且该元素必须大于44, 然后交换它们。因为55大于44, 所以交换它们。

22 33 11 44 77 90 40 60 99 55 88

递归地, 重复步骤1和步骤2, 直到获得两个列表, 其中一个列表位于枢轴元素44的左侧, 另一列表则位于枢轴元素的右侧。

22 33 11 40 77 90 44 60 99 55 88

与77交换：

22 33 11 40 44 90 77 60 99 55 88

现在, 右侧和左侧的元素分别大于和小于44。
现在我们得到两个排序列表：

文章图片
这些子列表的排序与上述过程相同。
这两个排序的子列表并排。

文章图片

文章图片
合并子列表：

文章图片
排序列表
最坏的情况分析：在这种情况下, 项目已经采用排序形式, 而我们尝试再次对其进行排序。这将花费大量时间和空间。
方程：

T (n) =T(1)+T(n-1)+n

T（1）是枢轴元素花费的时间。
T（n-1）是除枢轴元素外其余元素所花费的时间。
N：确定自身（每个元素）确切位置所需的比较次数
如果我们将第一个元素枢轴与其他元素枢轴进行比较, 那么将有5个比较。
这意味着如果有n个项目, 将有n个比较。

文章图片
最坏情况的关系公式：

文章图片
注意：为了将T（n-4）设为T（1）, 我们将（n-1）替换为’ 4′ , 如果我们将（n-1）替换为4, 则必须将（n- 2）代替3, （n-3）代替2, 依此类推。
T（n）=（n-1）T（1）+ T（n-（n-1））+（n-（n-2））+（n-（n-3））+（n-（ n-4））+ n T（n）=（n-1）T（1）+ T（1）+ 2 + 3 + 4 + … … … … n T（n） =（n-1）T（1）+ T（1）+ 2 + 3 + 4 + … … … .. + n + 1-1
[制作AP系列时加1减1]
T（n）=（n-1）T（1）+ T（1）+1 + 2 + 3 + 4 + … … .. + n-1 T（n）=（n-1） T（1）+ T（1）+ -1
停止条件：T（1）= 0
因为最后只剩下一个元素, 所以不需要比较。
T（n）=（n-1）（0）+ 0 + -1

文章图片
快速排序的最坏情况复杂度是T（n）= O（n2）
随机快速排序[平均情况]：
通常, 我们假定列表的第一个元素为枢轴元素。在平均情况下, 获得枢轴元素的机会数量等于项目数量。

Let total time taken =T (n) For eg: In a given list p 1, p 2, p 3, p 4............pn If p 1 is the pivot list then we have 2 lists. I.e. T (0) and T (n-1) If p2 is the pivot list then we have 2 lists. I.e. T (1) and T (n-2) p 1, p 2, p 3, p 4............pn If p3 is the pivot list then we have 2 lists. I.e. T (2) and T (n-3) p 1, p 2, p 3, p 4............p n

因此, 一般而言, 如果我们将Kth元素用作枢轴元素。
然后,

文章图片
枢轴元素将不进行比较, 而我们正在做平均情况,

文章图片
因此, 随机快速排序的关系公式为：

= n+1 +(T(0)+T(1)+T(2)+...T(n-1)+T(n-2)+T(n-3)+...T(0)) = n+1 +x2 (T(0)+T(1)+T(2)+...T(n-2)+T(n-1))

n T (n) = n (n+1) +2(T(0)+T(1)+T(2)+...T(n-1)........eq 1

将n = n-1放在等式1中

(n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2

从eq1和eq 2
n T（n）-（n-1）T（n-1）= n（n + 1）-n（n-1）+2（T（0）+ T（1）+ T（2）+？ T（n-2）+ T（n-1））-2（T（0）+ T（1）+ T（2）+ … T（n-2））n T（n）-（n -1）T（n-1）= n [n + 1-n + 1] + 2T（n-1）n T（n）= [2+（n-1）] T（n-1）+ 2n n T（n）= n + 1 T（n-1）+ 2n