用html5做的网站源码,今天新闻头条,网站建设与维护前景,js网站模板怎么用前言 本文是B站公开课《MIT算法导论》的随课笔记#xff0c;对于笔记内容和格式有问题的朋友欢迎私信或评论区交流~ 快速排序算法也是分治算法的应用之一#xff0c;且是原地排序#xff08;在原来的数据区域进行元素重排#xff09;#xff0c;快速排序也十分实用。 一. …前言 本文是B站公开课《MIT算法导论》的随课笔记对于笔记内容和格式有问题的朋友欢迎私信或评论区交流~ 快速排序算法也是分治算法的应用之一且是原地排序在原来的数据区域进行元素重排快速排序也十分实用。 一. 快速排序的描述
快排中的分治策略
①Divide
选取一个关键元素并根据这个关键元素的大小把数组划分成两个子数组部分左边的子数组小于该关键元素右边的子数组中的元素≥该关键元素。
②Conquer
递归地处理两个子数组的排序问题
③Combine
在快排问题中结合这一步并不是很重要因为当划分完后并递归地处理完了两个子数组的排序问题整个数组就已经有序了。 在快排中最重要的步骤就是partition的步骤——找到一个切分元素将整个数组划分成两个子数组。 从这个角度出发你可以把快排问题理解成不断地递归地对数组进行划分操作。 快速排序的伪代码表示
1partition
int Partition(int A[],int p,int q){x ← A[p]i ← pfor j ← P1 to qdo if A[j]≤xthen i ← i1exch(A[i],A[j])exch(A[p],A[i])return i上面的代码主要思想 每次选用数组的首元素作为切分元素指针i及之前保存着小于等于切分元素的所有元素指针i到j之间存放着大于或等于切分元素的所有元素指针j之后的元素是还没有进行比较的元素每一次审核元素时如果元素大于切分元素则指针j继续后移即可如果当前元素小于切分元素将当前元素和i1指向的元素进行交换按照第一点指针i1指向的元素一定是当前比较过的第一个大于切分元素的再把指针i和j均后移一位。最后循环完毕后将切分元素和指针i指向的元素进行交换返回下标i作为该轮切分之后的下标。 书本《算法导论》上给的伪码思想是一样的只不过是选择数组的末尾元素作为切分元素。
我在算法课上接触到的partition的实例思路大致相同——选择切分元素再维护指针与切分元素进行比较对大小关系不符合的元素进行交换。但是那时候是双指针同时扫描
int partition(int a[],int lo, int hi){int i lo,j hi1;int v a[lo];//切分元素while(true){while(less(a[i],v) if(i hi) break;while(less(v,a[--j])) if( j lo) break;if( i j) break;//当指针i和j相遇时主循环就会退出exch(a,i,j);}exch(a,lo,j);//将v a[j]放入正确的位置return j;}在循环中a[i]小于v时我们增大ia[j]大于v的时候我们减小j然后交换a[i]和a[j]来保证i左侧的元素都不大于vj右侧的元素都不小于v。当指针相遇时交换a[lo]和a[j]切分结束——这样切分值就留在a[j]中了。 在算法这本书中摘抄的partition实现代码其代码为了追求对称性在下标初始化上会有一些特殊不用深究。 不论是哪一种实现切分这一过程的时间复杂度大概维持在θ(n)上因为整个过程相当于是把数组中所有元素都遍历了一遍。 2quicksort 3改进tips
①对于代码“if(p q)”进行调整
代码为if(pq)的时候说明当处理的数组的元素为0个或1个的时候是没有工作量的。
可以针对这个进行改进寻找一个合适的算法当元素数目较少的时候可以改进排序的效率。 【这一点在归并算法的改进中也有实现《归并排序算法的实现与分析》】
②根据快排的伪代码可以知道算法是尾递归的因此可以使用一些尾递归的优化过程。
关于尾递归的一些概念可以参考【Allen Chou】这个博主的文章《详解什么是尾递归通俗易懂示例讲解》 快排的过程示例 说明上述过程是建立在partition的实现二得到的也就是选取数组的最后一个元素作为切分元素的结果。 二. 快排的复杂度分析
先给出结论本部分会针对复杂进行很多“有意思”的推导过程 快速排序的运行时间与划分是否对称有关而划分是否对称很大程度上取决于选择了哪一个划分元素。 如果划分是对称的那么快排从渐进意义上与归并排序具有一样的复杂度 如果划分不对称那么快排从渐进意义上与插入排序具有一样的复杂度。 1. 最坏情况划分
快排的最坏情况划分行为发生在划分过程产生的两个区域分别包含n-1个元素和1个0元素的时候从整个数组的角度来看也就是数组整体是顺序或者逆序时。
假设每一次划分都采用了不对称划分且划分的时间代价为θ(n)对一个零元素的数组进行递归调用的开销T(0)设为θ(1)则有 则算法运行时间的递归表达式如下图所示 直观来看如果将每一层递归的代价进行相加应该就能得到一个算术级数从而能推得其代价是平方级别的。 由此可看快排最坏情况下和插入排序的平均性能是一致的。甚至在元素全部有序的情况下插入排序仅仅需要线性的时间复杂度O(n)。 递归树如下所示 p.s. 图有点高糊请见谅 如上图得到的递归树结构十分不平衡则树的高度为n因为每一层都是往下减一所有的根节点的复杂度总和加起来是平方级别所有叶子节点一共有n个的复杂度为θ(1)其总和是线性级别。 故总和就是θ(n2)θ(n) θ(n2)。 2. 最好情况分析
1复杂度递推公式
在划分步骤中所得达到的最平衡的划分得到的两个子问题的大小都不可能大于n/2在这种情况下快速排序的运行速度要快得多。 推导此时的复杂度递推公式则有
2平衡的划分
即使在知道快排的最坏情况为平方级别的复杂度的情况下我们依然高度认可快排的效率是因为从平均情况看快排的效率也是线性对数级别的。 快排的平均情况接近于最佳情况的运行时间而非最坏情况的运行时间要理解这一点就要理解划分的平衡性是如何在刻画运行时间的递归式中反映出来的。 假设划分过程总是产生9:1的划分 此时复杂度的递归式就写作 T(n) T(n/10)T(9n/10)θ(n) ≤ T(n/10)T(9n/10)cn
为上述递归式建立一棵递归树有关树高以及每一层的计算代价的分析见下图 按照树的结构可以分析出来整个复杂度T(n)≤c·n·log10/9nθ(n)这个式子在渐进意义上得到的复杂度为O(nlogn) 从数学计算的角度不论对数运算的底数为多少都能通过对数运算性质把底数化成2然后多余的项作为系数提在整个对数项的外面。 3. 平均情况分析 要想对快速排序的平均情况有较为清楚的认识就要对各种输入的出现频率做个假设。 但是对一个随机的输入数组应用快排时假设每一层都有相同的划分与分布是不太可能的。我们只能期待某些划分比较平衡而某些划分是不平衡的。 假设好的划分与坏的划分交替地出现在树的各层上 我们可以得到两组递归式与递归树
L(n) 2U(n/2) θ(n)-------Lucky U(n) L(n-1) θ(n) -------Unlucky 【使用代换法和主定理】 怎样确保我们总是能够有渐进最优的复杂度呢
将数组中的元素随机shuffle随机选择划分主元 我们通常考虑后者因为分析起来更加方便直观。 三. 快排的随机化版本
“很多时候我们可以向一个算法中加入随机化的成分以便对于所有输入它均能获得较好的平均情况性能”。 ——快排的随机化版本是对足够大的输入的理想选择。 【随机取样】 不是始终采用A[r]作为主元而是从子数组A[p…r]中随机选择一个元素即将A[r]与从A[p…r]中随机选出的一个元素进行交换再按照之前的逻辑进行快排。 在上述随机化操作中我们是从p,…r这个范围中随机取样的这样就确保了在子数组的r-p1个元素中主元元素x A[r]等可能地取其中的任何一个。 因为主元元素是随机选择的我们期望在平均情况下对输入数组的划分能够比较对称。 1. 随机化快排的优势
①运行时间不依赖于输入序列的顺序 ②无需对输入序列的分布做任何假设 ③不会有那种特定的输入导致最坏情况的发生最坏情况只有随机数生成器决定。
2. 随机化快排的伪码
