网站建设费可以计业务费吗,wordpress 08影院,flash网站制作工具,山西网站建设平台文章目录 1. 不稳定 就地2. 最好情况 最坏情况3.平均情况 1. 不稳定 就地
以下针对刚才所给出的快速排序算法的第一个版本#xff0c;就其性能做一分析。
首先很遗憾地发现#xff0c;这个算法是不稳定的。快速排序算法的不稳定性通过我们刚才所举的那个实例可以清楚地看… 文章目录 1. 不稳定 就地2. 最好情况 最坏情况3.平均情况 1. 不稳定 就地
以下针对刚才所给出的快速排序算法的第一个版本就其性能做一分析。
首先很遗憾地发现这个算法是不稳定的。快速排序算法的不稳定性通过我们刚才所举的那个实例可以清楚地看出来。 注意到在原始的输入序列中有两个5按照先后次序我们分别用5A 和5B 来表示。
在经过一次划分之后我们可以看到这两个元素的位置已经彼此颠倒。实际上这种现象必然是普遍存在的。因为对于任何两个小于候选轴点的元素而言它们加入子序列 L 的次序必然是颠倒的。同理对于大于候选轴点的雷同元素而言也有对称的性质。
其次整个算法也是可以就地实现的也就是说它只需要常数的附加空间。这一点从刚才这组原理和过程图中也可以清晰地看出。 实际上除了原始的输入序列我们这里只需要维护常数个指针以及用于保存候选轴点的一个单元。
2. 最好情况 最坏情况 那么整个算法的运行时间呢我们知道对于归并排序而言整个算法的运行时间可以保证不超过 n*log n。我们也知道其关键在于归并排序可以保证任何一对被划分出来的子任务在规模上都是彼此相当的也就是规模都接近二分之N。因此总体的运行时间也就是求解两个这样的问题再加上为了将它们的结果合并所需要的线性时间。
很遗憾快速排序算法却不能像归并排序算法那样保证子任务划分时的均衡性。实际上partition 算法的每次划分结果与其说是取决于这个算法不如说取决于最初选定的候选轴点。
如果候选轴点在最终有序列中所对应的秩为 r那么经划分之后所得到的序列 L 的长度也必然就是 r。而对应的子序列 G 的长度也必然为 n 减 1 再减 r。划分的结果是否均衡完全取决于我们的运气。 在最好的情况下我们的每次划分都是均衡的或者至少是接近均衡的于是我们自然可以达到最优的 n*logn。 然而反过来在最坏的情况下有可能我们的每一次划分都不均衡甚至极不均衡。比如最为极端的一种情况就是每一个候选节点都是在当前而言最小或者最大的极值元素以至于在划分之后子序列 L 为空或者 G 为空。也就是说在我们所划分出来的一对子任务中总是有一个规模为零而另一个相对于此前的规模只减少了一个单位。 根据这个递推式不难解出此时算法所需要的总体运行时间必然是平方量级的。也就说与起泡排序等低级算法居然性能是相当的。
当然采用一些简明的策略在付出足够小的代价之后我们的确可以在一定程度上降低最坏情况出现的概率。比如我们可以采用所谓随机选取法也就说不再是每次都固定地将首元素作为候选轴点。而是在整个序列中随机地选择其一。另一种更为有效的方法是所谓的三者取中法也就是说我们每次都是在整个序列中随机地抽取3个元素然后将其中数值居中的那个作为候选轴点。
当然无论采用什么方法我们也只能是在一定程度上降低最坏情况出现的概率而无法根本的杜绝最坏情况的出现。既然如此我们接下来不得不回答的一个问题就是就基本的快速排序算法而言其平均性能又有多高呢
3.平均情况
非常幸运的是以上基本的快速排序算法在常规的随机意义下平均性能的确可以达到最优的 n log n。
以下我们不妨针对最为常见的均匀独立分布来做一精确的估算也就说我们在这里假设所有的元素都是均匀的取自于某一个数值范围。同时各元素在确定各自取值时是互不依赖的。
我们来考察任何一个这样的随机序列调用 partition 算法对它进行的划分将有几种可能呢无非 n 种可能具体的哪种情况完全取决于最初所选定的那个候选轴点。
更准确地讲是这个候选轴点在最终有序列中所具有的秩。如果将候选轴点的这个秩记作 k那么 partition 算法所输出的子序列 L 长度也应该是 k这个子序列所对应的那个子任务所需的平均运行时间也因此就可以表示为Tk。对称的 partition 算法所输出的子序列 G 长度应该为 n 减 k 减1这个子序列所对应的那个子任务从递归的角度来看所需要的平均运行时间也因此可以表示为 T n 减 k 再减1。这样的一对排序子任务总共所需要的运行时间也自然就是二者之和。
进一步的既然按照假设这里服从均匀独立分布因此各种情况出现的概率应该均等。具体来说都是 n 分之1。因此所有这些情况所对应的平均运行时间也就是用这个概率对它们的总和进行平均。以下的分析焦点就会聚在这个求和号上。尽管这个求和涉及到前后两个序列但是略加观察之后我们不难发现这两个序列的求和应该完全是相等的你能看出原因来吗
没错这两个序列的取值范围都是从 0 到 n 减1 只不过前者是递增的从0到 n 减1而后者只不过是递减的从 n 减1到0。因此我们只需保留其中的一项同时作为补偿将它的系数加倍。
接下来我们将这个等式的两端同时乘以 n于是就可以得到这样一个等式。如果将其中所有的 n 都替换为 n 减1我们又可以进而得到下面这个等式。现在我们只需将这两个等式相减就可以得到这样一个等式。除了系数这个等式主要都包含一个 Tn 以及两个 T n 减一。
接下来我们只需对 Tn 和 Tn 减1合并同类项就可以得到这样一个等式。对于这样一个等式我们不妨令它的左右两端同时除以 n 以及 n 加1。
于是就可以得到这样一个等式如果我们将这个等式的左侧表示和理解为另一个函数 Sn那么右侧的这一项也就对应于 Sn 减1。这样我们也得到了一个关于 Sn 的简明递推式。
因此接下来我们可以进而将右侧的 Sn 减 1 替换为 Sn 减2。当然为此我们需要追加一项这种地推可以持续进行下去也就说我们可以将 Sn 减2替换为 Sn 减3再将 Sn 减3替换为 Sn 减4以及 Sn 减4替换成 Sn 减5诸如此类。
在递推到最终一步之前我们所引入的各项将构成一个级数。你应该看得出来这是一个什么级数。没错调和级数。我们在第一章就曾介绍过就渐进意义而言调和级数是与自然对数 log n 同阶的。
由此可见我们这里所需要估计的快速排序算法的平均运行时间在渐进意义下的确不超过 n * log n那么它对应的常系数呢为此我们只需将 log n 替换为以2为底的对数相应的也自然可以得知常系数应为两倍的 ln2具体来说也就大致为1.39。
这样小的一个长系数也保证了快速排序算法在通常情况下的优异性能也就是说快速排序的确名符其实。
