快速排序算法

本文概述

它是分而治之类型的算法。

除法:重新排列元素并将数组拆分为两个子数组, 并在两次搜索之间的一个元素中, 左子数组中的每个元素小于或等于平均元素, 右子数组中的每个元素大于中间元素。

征服:递归地, 对两个子数组进行排序。

合并:合并已排序的数组。

算法

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

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

DAA快速排序

快速排序示例:

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。

现在我们得到两个排序列表:

DAA快速排序

这些子列表的排序与上述过程相同。

这两个排序的子列表并排。

DAA快速排序
DAA快速排序

合并子列表:

DAA快速排序

排序列表

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

方程:

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

T(1)是枢轴元素花费的时间。

T(n-1)是除枢轴元素外其余元素所花费的时间。

N:确定自身(每个元素)确切位置所需的比较次数

如果我们将第一个元素枢轴与其他元素枢轴进行比较, 那么将有5个比较。

这意味着如果有n个项目, 将有n个比较。

DAA快速排序

最坏情况的关系公式:

DAA快速排序

注意:为了将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

DAA快速排序

快速排序的最坏情况复杂度是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元素用作枢轴元素。

然后,

DAA快速排序

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

DAA快速排序

因此, 随机快速排序的关系公式为:

= 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

DAA快速排序

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

DAA快速排序

将4 eq放入3 eq

DAA快速排序

将n = n-2放在等式3中

DAA快速排序

将6 eq放入5 eq

DAA快速排序

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

DAA快速排序

将8 eq放入7 eq

DAA快速排序
DAA快速排序

从3eq, 5eq, 7eq, 9eq得到

DAA快速排序
DAA快速排序

从10当量

DAA快速排序

将最后一项乘以2

DAA快速排序

是对n个元素进行排序的快速排序的平均用例复杂度。

3.快速排序[最佳情况]:在任何排序中, 只有在只有一个要排序的元素时才对元素进行任何比较, 这是唯一的情况。

DAA快速排序

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?