企业官网建设流程全解析

网站建设技术服务费怎么入账,营销型品牌网站建设,移动端网站的优点,域名查询大全过程 快速排序分为三个过程#xff1a; 将数列根据划分值 mmm 划分为两部分#xff1b;递归到两个子序列中分别进行快速排序#xff1b;不用合并#xff0c;因为此时数列已经完全有序。 具体来说#xff0c;第一步要是要把数列分成两个部分#xff0c;然后保证前一个子…过程快速排序分为三个过程将数列根据划分值m mm划分为两部分递归到两个子序列中分别进行快速排序不用合并因为此时数列已经完全有序。具体来说第一步要是要把数列分成两个部分然后保证前一个子数列中的数都小于后一个子数列中的数。对于最优情况每一次选择的分界值都是序列的中位数。快速排序与归并排序虽然都是划分区间但是归并排序直接就可以选取中间位置但快速排序需要选择的是中间数值中间位置你是可以直接确定的而中间数值你是无法确定的。为了保证平均时间复杂度一般是随机选择一个数m mm来当做两个子数列的分界。其实快速排序没有指定应如何具体实现第一步不论是选择m mm的过程还是划分的过程都有不止一种实现方法。第三步中的序列已经分别有序且第一个序列中的数都小于第二个数所以直接拼接起来就好了。在实现时只需维护小于等于m mm的边界l o w lowlow大于m mm的部分自然就唯一确定了。朴素快速排序publicstaticvoidquickSort(intl,intr){if(lr)// 只有一个数或范围不存在return;intxarr[l];// 固定方式选取划分值intmidpartition(l,r,x);// mid 位置已经固定// 处理剩余区间quickSort(l,mid-1);quickSort(mid1,r);}// 划分数组 ≤x 放左边x 放右边publicstaticintpartition(intl,intr,intx){intlowl,xi0;for(intil;ir;i){if(arr[i]x){swap(low,i);if(arr[low]x)xilow;low;}}swap(xi,low-1);// 确保 ≤x 区域的最后一个数字是 xreturnlow-1;}这里再贴一个 c 风格的双指针扫描写法的 partition常见于数据结构教材中。intpartition(intlow,inthigh,intx){while(lowhigh){while(lowhigharr[high]x)high--;swap(low,high);while(lowhigharr[low]x)low;swap(low,high);}returnlow;}时间复杂度快速排序的最优时间复杂度和平均时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)最坏时间复杂度为O ( n 2 ) O(n^2)O(n2)。对于最优情况每一次选择的分界值都是序列的中位数此时算法时间复杂度满足的递推式为T ( n ) 2 T ( n 2 ) Θ ( n ) T(n) 2T\left( \frac{n}{2} \right)Θ(n)T(n)2T(2n​)Θ(n)由主定理T ( n ) Θ ( n log ⁡ n ) T(n)Θ(n\log n)T(n)Θ(nlogn)。对于最坏情况每一次选择的分界值都是序列的最值此时算法时间复杂度满足的递推式为T ( n ) T ( n − 1 ) Θ ( n ) T(n)T(n-1)Θ(n)T(n)T(n−1)Θ(n)易得T ( n ) Θ ( n 2 ) T(n)Θ(n^2)T(n)Θ(n2)。对于平均情况每一次选择的分界值可以看作是等概率随机的设划分值在k kk位置那么T ( n ) 1 n ∑ k 1 n ( T ( k − 1 ) T ( n − k ) ) n 2 n ∑ k 1 n T ( k ) n T(n)\frac{1}{n}\sum_{k1}^n(T(k-1)T(n-k))n\frac{2}{n}\sum_{k1}^nT(k)nT(n)n1​k1∑n​(T(k−1)T(n−k))nn2​k1∑n​T(k)n由数学归纳法可证明其数量级为O ( n log ⁡ n ) O(n\log n)O(nlogn)。在实际中几乎不可能达到最坏情况而快速排序的内存访问遵循局部性原理递归处理相邻子数组、原地分区连续访问缓存行所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)的排序算法。就空间复杂度而言主要是递归造成的栈空间的使用最好情况递归树的深度为log ⁡ 2 n \log_{2}nlog2​n其空间复杂度也就为O ( log ⁡ n ) O(\log n)O(logn)最坏情况需要进行n − 1 n-1n−1递归调用其空间复杂度为O ( n ) O(n)O(n)平均情况空间复杂度也为O ( log ⁡ n ) O(\log n)O(logn)。优化当序列较短时直接使用插入排序的效率更高尾递归迭代可以缩减堆栈深度提高整体性能。我们还有两条主路径去优化划分值m mm的选取和划分的过程。划分值m mm如果你用朴素方法中的固定方式选取划分值m mm比如总选数列第一个或最后一个元素毒瘤数据能够把朴素的快速排序卡成O ( n 2 ) O(n^2)O(n2)比如升序或降序数列。通过三数取中即选取第一个、最后一个以及中间的元素中的中位数。对于非常大的待排序的数列也有九数取中不再详述。通过随机选取即随机选一个[ l , r ] [l,r][l,r]上的下标对应的值。虽然随机的常数时间比较大但只有这一下随机才能在概率上把快速排序的时间复杂度收敛到O ( n log ⁡ n ) O(n\log n)O(nlogn)。划分过程朴素方法中每次划分的过程都只能确定一个位置的值即p a r t i t i o n partitionpartition返回的位置。三路快速排序是快速排序和基数排序的混合。思想基于 荷兰国旗问题。每次划分过程将待排数列划分为三个部分小于m mm、等于m mm以及大于m mm。在处理含有多个重复值的数组时效率远高于朴素快速排序。其最佳时间复杂度为O ( n ) O(n)O(n)。在实现时只需维护小于m mm的边界和大于m mm的边界等于的部分自然就唯一确定了。荷兰国旗优化版随机快速排序publicstaticintfirst,last;publicstaticvoidquickSort(intl,intr){if(lr)return;// [l, r1) - l [0, r-l1)intxarr[l(int)(Math.random()*(r-l1))];partition(l,r,x);intleftfirst;intrightlast;// 记录一下 lastquickSort(l,left-1);// 经过左半边快排last 可能被更改quickSort(right1,r);}publicstaticvoidpartition(intl,intr,intx){firstl;lastr;intil;while(llast){if(arr[i]x)i;elseif(arr[i]x)swap(first,i);elseswap(last--,i);}}内省排序是快速排序和堆排序的结合。保证了最差时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)。内省排序将快速排序的最大递归深度限制为⌊ log ⁡ n ⌋ \lfloor \log n \rfloor⌊logn⌋超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性又可以防止快速排序在某些情况下性能退化为O ( n 2 ) O(n^2)O(n2)。SGI C STL 的stl_algo.h中sort()函数的实现采用了内省排序算法。习题洛谷 P1177【模板】快速排序 模板力扣 912. 排序数组 模板#atom