当前位置： 首页 > news >正文

自己做电商网站,工作简历模板电子版,wordpress文件名乱码,烟台做网站建设文章目录 1. 快速排序的描述 1.1基本描述1.2 PARTITOION函数1.3 快速排序C完整代码 2. 快速排序的性能2.1 最坏时间复杂度2.2 平均时间复杂度 1. 快速排序的描述
1.1基本描述 快速排序是一种时间复杂度为 O(n^2) 的排序算法。虽然最坏情况时间复杂度很差#xff0c;但他的平… 文章目录 1. 快速排序的描述 1.1基本描述1.2 PARTITOION函数1.3 快速排序C完整代码 2. 快速排序的性能2.1 最坏时间复杂度2.2 平均时间复杂度 1. 快速排序的描述
1.1基本描述 快速排序是一种时间复杂度为 O(n^2) 的排序算法。虽然最坏情况时间复杂度很差但他的平均性能却很好它的期望时间复杂度是 O(nlgn) 而且 O(nlgn) 中隐含的常数因子很小大约是1.44左右。   快速排序与归并排序一样也是基于归并的思想以下是对其子数组 A[ p…r ] 进行快速排序三步分治的过程 分解数组 A[ p…r ] 被划分为两个子数组 A[ p…q-1] 和 A[q1…r]使得 A[ p…q-1]中的每一个元素都小于等于 A[ q ] 而 A[ q ]也小于等于 A[ q1…r]中的每一个元素。 解决通过递归调用快速排序对子数组A[ p…q-1] 和 A[q1…r]进行排序。 合并因为子数组都是原址排序的所以并不需要合并操作A[ p…r ] 已经有序。 快速排序伪代码 QUICKSORT(A,p,r)if p rq PARTITION(A, p ,r)QUICKSORT(A, p ,q-1)QUICKSORT(A, q1 ,r)其中q PARTITION(A, p ,r) 所执行的操作就是分解操作并返回 q。 1.2 PARTITOION函数 ​ PARTITION函数伪代码 PARTITION(A, p, r) x A[r] i p - 1 for j p to r - 1 do if A[j] ≤ xthen i i 1 exchange A[i] with A[j] exchange A[i 1] with A[r] return i 1PARTITION函数思路简介   其中 0 - i 维护的是小于等于A[ r ] 的序列A[ i1 ] 即为比 A[ r ] 大的第一个数j从开始节点遍历到倒数第二个节点遇到比 A[ r ] 小的数便进行 A[ j ] 与 A[ i1 ] 的交换以此维护了 0 - i 序列中比 A[ r ]小的特性。j 遍历完成后即实现了A[0…i] 小于等于 A[ r ] A[i1…j] 大于 A[ r ]。 PARTITION函数执行过程
1.3 快速排序C完整代码

include iostream

using namespace std; int PARTITION(int A[],int p,int r) {int x A[r];int i p - 1;for(int j p; j r - 1; j){if(A[j] x){i i 1;swap(A[i],A[j]);}}swap(A[i1] , A[r]);return i1; } void QUICKSORT(int A[],int p,int r) {if(p r){int q PARTITION(A,p,r);QUICKSORT(A,p,q-1);QUICKSORT(A,q1,r);} } int main() {int A[100010];int n;cinn;for(int i0;in;i){cinA[i];}QUICKSORT(A,0,n-1);for(int i0;in;i){coutA[i] ;}return 0; }2. 快速排序的性能 2.1 最坏时间复杂度 因为无法举出使快速排序达到最坏情况的例子所以我们通过两步证明其最坏时间复杂度为 O( n^2 ) 举一个例子证明其时间复杂度为 O( n 2 n^2 n2) 当对快速排序进行分解的过程中得到的结果为一部分为 n 个元素另一部分为0个元素时该例的运行时间递归式为 T ( n ) T ( n − 1 ) T ( 0 ) θ ( n ) T ( n − 1 ) θ ( n ) \begin{aligned}T(n) T(n-1)T(0)\theta(n)\ T(n-1)\theta(n) \end{aligned} T(n)​T(n−1)T(0)θ(n)T(n−1)θ(n)​可以得到 T ( n ) θ ( n 2 ) T(n)\theta(n^2) T(n)θ(n2) 由此可知 Quicksort 的最坏运行时间为 Ω( n 2 n^2 n2)证明其时间复杂度不超过 O( n 2 n^2 n2) 设T(n)是对大小为 n 的输入进行快速排序的最坏情况时间则有递归 T ( n ) max ⁡ 0 ≤ q ≤ n − 1 ( T ( q ) T ( n − q − 1 ) ) C 1 n T(n)\max_{0 \leq q\leq n-1}(T(q)T(n-q-1))C1n T(n)0≤q≤n−1max​(T(q)T(n−q−1))C1​n我们猜测对于某个常数C使得T (n) ≤ C将这个猜测代入上面的递推式我们得到 T ( n ) ≤ max ⁡ 0 ≤ q ≤ n − 1 ( C q 2 C ( n − q − 1 ) 2 ) C 1 n C ∗ max ⁡ 0 ≤ q ≤ n − 1 ( q 2 ( n − 1 − q ) 2 ) C 1 n \begin{aligned}T(n)\leq \max{0 \leq q\leq n-1}(Cq^2C(n-q-1)^2)C1n\C* \max{0 \leq q\leq n-1}(q^2(n-1-q)^2)C1n\end{aligned} T(n)​≤0≤q≤n−1max​(Cq2C(n−q−1)2)C1​nC∗0≤q≤n−1max​(q2(n−1−q)2)C1​n​由于 q 2 ( n − 1 − q ) 2 q^2(n-1-q)^2 q2(n−1−q)2 是 q q q 的二次函数求导可得在区间 [1… n ] 范围内该函数只可能在 q 1 q n q n / 4 q 1q nq n/4 q1qnqn/4等三个点处取极值由此可知 ∑ 0 ≤ q ≤ n − 1 ( q 2 ( n − 1 − q ) 2 ) ≤ n 2 \sum{0 \leq q\leq n-1}(q^2(n-1-q)^2) \leq n^2 0≤q≤n−1∑​(q2(n−1−q)2)≤n2所以有 T ( n ) ≤ C ( n − 1 ) 2 C 1 n C ∗ n 2 − 2 C n C 1 n C T(n)\leq C(n-1)^2C_1nC*n^2-2CnC_1nC T(n)≤C(n−1)2C1​nC∗n2−2CnC1​nC当取 C C1 时 T ( n ) C n 2 T (n)Cn^2 T(n)Cn2 对所有 n 1 n 1 n1 成立由此证得快速排序时间复杂度不超过 O( n 2 n^2 n2)。 2.2 平均时间复杂度 设 T ( n ) T (n) T(n) 为输入规模为 n 时 QUICKSORT 算法的平均运行时间 T k ( n ) Tk(n) Tk​(n)为所选划分元序号为 k1 时 QUICKSORT 算法的平均运行时间则 T ( n ) T (n) T(n) 满足以下递归方程 T ( n ) ∑ k 0 n − 1 ( p ( k 1 ) T k ( n ) ) T(n)\sum{k0}^{n-1} (p(k1)Tk(n)) T(n)k0∑n−1​(p(k1)Tk​(n))其中 p ( k 1 ) p(k1) p(k1)为划分元素序号为 k 1 k1 k1的概率我们可以知道划分元素序号的概率是相同的故 p ( k 1 ) 1 n p(k1)\frac{1}{n} p(k1)n1​带入上式可得 T ( n ) ∑ k 0 n − 1 1 n T k ( n ) ) 1 n ∑ k 0 n − 1 ( T ( k ) T ( n − k − 1 ) c n ) T(n)\sum{k0}^{n-1} \frac{1}{n}Tk(n)) \frac{1}{n}\sum{k0}^{n-1} (T(k)T(n-k-1)cn) T(n)k0∑n−1​n1​Tk​(n))n1​k0∑n−1​(T(k)T(n−k−1)cn)继续化简可得 1 n ( ∑ k 0 n − 1 T ( k ) ∑ k 0 n − 1 T ( n − k − 1 ) ) c n 2 n ∑ k 0 n − 1 T ( k ) c n \frac{1}{n}(\sum{k0}^{n-1} T(k)\sum{k0}^{n-1}T(n-k-1))cn\frac{2}{n}\sum{k0}^{n-1}T(k)cn n1​(k0∑n−1​T(k)k0∑n−1​T(n−k−1))cnn2​k0∑n−1​T(k)cn解递归方程可得 n T ( n ) 2 ∑ k 0 n − 1 T ( k ) c n 2 nT(n)2\sum{k0}^{n-1}T(k)cn^2 nT(n)2k0∑n−1​T(k)cn2 ( n − 1 ) T ( n − 1 ) 2 ∑ k 0 n − 1 T ( k ) c n 2 (n-1)T(n-1)2\sum{k0}^{n-1}T(k)cn^2 (n−1)T(n−1)2k0∑n−1​T(k)cn2两式相减可得 n T ( n ) − ( n − 1 ) T ( n − 1 ) 2 T ( n − 1 ) c ( 2 n − 1 ) nT(n)-(n-1)T(n-1)2T(n-1)c(2n-1) nT(n)−(n−1)T(n−1)2T(n−1)c(2n−1) T ( n ) n 1 T ( n − 1 ) n 2 c n \frac{T(n)}{n1}\frac{T(n-1)}{n}\frac{2c}{n} n1T(n)​nT(n−1)​n2c​令 G ( n ) T ( n ) ( n 1 ) G(n) \frac{T(n)}{(n1)} G(n)(n1)T(n)​则有 G ( n ) ≤ C ( n − 1 ) 2 c n G ( n − 2 ) 2 c ( 1 n − 1 1 n ) G ( n − 3 ) 2 c ( 1 n − 2 1 n − 1 1 n ) G ( n − k ) 2 c ( 1 n − k 1 … 1 n − 1 1 n ) \begin{aligned}G(n) \leq C(n-1)\frac{2c}{n}\G(n-2)2c(\frac{1}{n-1}\frac{1}{n})\G(n-3)2c(\frac{1}{n-2}\frac{1}{n-1}\frac{1}{n})\G(n-k)2c(\frac{1}{n-k1}…\frac{1}{n-1}\frac{1}{n}) \end{aligned} G(n)​≤C(n−1)n2c​G(n−2)2c(n−11​n1​)G(n−3)2c(n−21​n−11​n1​)G(n−k)2c(n−k11​…n−11​n1​)​整理后得到 G ( 1 ) 2 c ∑ k 0 n − 2 1 n − k 2 c ∑ k 2 n 1 k 2 c ∗ H n 2 c l o g n G(1)2c\sum{k0}^{n-2}\frac{1}{n-k}2c\sum_{k2}^{n}\frac{1}{k}2c*H_n2clogn G(1)2ck0∑n−2​n−k1​2ck2∑n​k1​2c∗Hn​2clogn 所以Quicksort 算法的平均时间复杂度为 T ( n ) G ( n ) ( n 1 ) θ ( n l o g n ) T(n)G(n)(n1)\theta(nlogn) T(n)G(n)(n1)θ(nlogn) ​