赞
踩
归并排序和快速排序都使用了分治法,但二者又有区别。
归并排序的计算量和难点在于合(子任务的解进行合并),而快速排序在于分(子任务或子序列的划分)
归并排序是分治策略在算法中的又一典型。
T(n) = 2T(n/2) + O(n) = O(nlogn)
归并排序的最好,最坏,平均时间复杂度都为O(nlogn)。
空间复杂度是O(n)。在合并的过程中采用了tmp临时数组。
是稳定排序算法。
这是基于分治法的又一典型算法。
将序列分为两个子序列 S= SL + SR // O(n)
在子序列分别递归的排序之后,原序列自然有序
平凡解:只剩单个元素时,本身就是解
轴点(pivot):凡是居于它左侧的元素都不比它更大,凡是居于它右侧的元素都不比它更小。
以任意一个轴点为界,原序列可划分成左小右大两个子序列:
[lo, hi) = [lo, mi) + [mi] + (mi, hi)
所以如果我们可以在任意一个序列中找到轴点,那么我们可以通过递归得到有序序列。所以快速排序的核心就在于如何找到轴点
然而在原始序列中,轴点未必是存在的。如任何一个有序序列只要经过一次循环移位,就可得到不存在轴点的序列(2、3、4、……、n、1)。虽然轴点未必天然存在,但是我们可以适当地交换,可使任一元素转换为轴点。
我们可知在有序序列中,所有元素都是轴点。同样的只要一个序列中的所有元素都是轴点,那么这个序列就是有序的。所以快速排序可以看做是将所有元素逐个转换为轴点的过程。
首先随机选取一个数作为轴点候选,通常取作首元素。而后使用两个指针lo和hi,这两个指针可以将序列分为三个L、U、G子序列。其中L<=pivot,pivot<=G,而U是尚未排序的序列。初始状态下U是整个序列,而L、G皆为空。在算法进行过程中,lo和hi相互接近,扩大L和G,缩小U。
在算法进行过程中要保证:
在初始状态下,无论L和G都是空的,所以第一条满足。同样的,由于首元素已经作为轴点候选被取出备份,所以elem[lo]是(逻辑上)空闲的。
接下来,检查U的末元素elem[hi],如果pivot <= elem[hi]则hi–。之前的元素自动的归入G中,而U少了一个元素。这个过程重复执行下去直至pivot > elem[hi],这时elem[hi]严格的满足了L的条件,则将其转换到空闲单元elem[lo]中,即elem[lo] = elem[hi]。尽管elem[lo]不再是空闲的,但elem[hi]则变成空闲的了。之后要做的正好与之前相反。这时再检查U的首元素elem[lo],如果elem[] <= pivot,则lo++。之前的元素自动的归入L中,而U少了一个元素。这个过程重复执行到pivot < elem[lo]。这时elem[lo]严格的满足了G的条件,则将其转换到空闲单元elem[hi]中。至此整个算法经历了一个完整的周期。反复执行上述过程,直至子序列U只剩下一个单元时,我们只需要将候选轴点植入这个空闲单元,这时它就成为了一个名副其实的轴点了。我们也完成了对原序列的一次快速划分。
不稳定、就地(只需要常数个指针以及一个保存候选轴点的空间)
由于划分的结果是否均衡,完全取决于我们的运气,所以
改进方案:改进选取枢轴的方法
1、选取随机数作为轴点。
但是随机数的生成本身是一种代价,根本减少不了算法其余部分的平均运行时间。
2、使用左端,右端和中心的中值做为轴点。
经验得知,选取左端,右端,中心元素的中值会减少了快排大约 14%的比较。
3、每次选取数据集中的中位数做轴点。
选取中位数的可以在 O(n)时间内完成。(证明见《算法导论(第二版) 》) P111 第九章中位数和顺序统计学:在平均情况下,任何顺序统计量(特别是中位数)都可以在线性时间内得到。
其他可以改进的地方 :
快速排序在处理小规模数据时的表现不好
这个时候可以改用插入排序。
当数据规模小于一定程度时,改用插入排序。具体小到何种规模时,采用插入排序,这个理论上还不解,一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10.
因为排序算法复杂度高,所以我们需要另辟蹊径
k-selection:在任意一组可比较大小的元素中,如何由小到大,找到次序为k者?
median:上述问题的特例是如何找到中位数?
虽然中位数是k选择问题的特例,但也是难度最大的问题。
蛮力:排序 + 扫描
1、尝试:堆A
堆结构的主要功能也是在做某种意义上的选取,也就是选取极值元素getMax()。而选取极值就是选取问题的特例。而选取问题也是getMax()的一般化推广。
这里我们需要的是小顶堆。连续调用k次delMin()后,整个堆的规模将变成n-k。而此时的堆顶应为所选取的元素。
就第一步建堆预处理Heapifiation()而言,性能并不差,只需要O(n)的时间,而delMin()的调用,时间却很长。每次都需要O(logn)的时间,总共是O(k*logn).
2、尝试:堆B
在数据集中任选k个元素,组织委大顶堆。(O(k))
再对于剩余的n-k个元素,各调用一次insert()和delMax()操作将其插入一个元素并删除一个元素(规模:k–>k+1–>k)。需要注意的是,每次当规模从k变为k+1时,对应的堆顶元素都是迄今为止发现的秩为k的那个元素。因此当所有元素都经过如此处理之后,当这个堆的规模最后一次到达k+1时,这时的堆顶元素就是全局秩为k的那个元素。(O(2*(n-k)*logk))
可是这个方法的时间复杂度依然不能得到有效地控制。
3、尝试:堆C
这里我们将使用两个而不是一个堆。
首先我们从数据集中取k个元素,构建大顶堆H。再将剩余的n-k个元素构建成小顶堆G。我们将反复比较两个堆顶,只要h>g,我们就令二者交换,然后分别通过一次下滤,将这两个堆复原。这个迭代将一直进行下去,直到h<=g。一旦达到这个状态,堆G的堆顶元素就是我们需要查找的目标。但是同样的,他在最坏情况下的复杂度依然不能得到有效控制。
借用partition算法实现的quickSelection()。
在最好情况下:选取的轴点就是我们要需要的第k个元素,这时的计算量只不过是O(n)。
虽然在一般情况下,轴点并不一定是我们需要的第k个元素,但这依然可以有效的削减问题的规模。
通过以上两种情况,我们都可以有效的削减问题的规模,这样一个削减的过程将持续进行下去。在整个问题的规模退化到平凡问题之前,我们迟早会找到目标元素
虽然在构造轴点的内循环,每趟只需线性的时间,但我们无法控制外循环的执行次数。虽然通常情况下外循环只需执行常数次,但在最坏情况下依然需要n次。因此就最坏情况而言,这个算法依然不是最优的。
在quickselect算法的基础上改进的选取算法,在最坏情况下也只需要线性的时间
需要用到常数Q
时间复杂度:
将linearSelect()算法的运行时间基座T(n)
第零步:O(1)= O(QlogQ)//递归基:序列长度|A| <= Q
第一步:O(n)//子序列划分,只需要坐一趟线性的扫描
第二步:O(n)= O(1) * n/Q//对每一组序列进行排序,并进而找到其中位数。
第三步:T(n/Q)//从上一步所得到的n/Q个中位数中,递归的找到全局的中位数
第四部:O(n)//根据全局中位数,将整个集合分为三个子集,并分别计数——只需要一趟扫描
第五步:T(3n/4)//递归的解决已经缩小的新问题,新问题的规模一定会被有效的削减。
为什么新问题的规模一定会被有效的削减?
T(n) = O(n) + T(n / Q) + T(3n / 4)
为使之解作线性函数,只需要保证:
n/Q + 3n/4 < n
或等价的
1/Q + 3/4 < 1
比如Q= 5,则存在常数c,使得
T(n) = cn + T(n/5) + T(3n/4)
T(n) = O(20cn) = O(n)
这的确是一个线性函数,但他的常系数很大,所以这个linearSelect()算法更多的是具有理论意义。
majority:在无序向量中,若有一半以上元素同为m,则称之为众数。
如在{3,5,2,3,3}中众数为3.
但在{3,5,2,3,3,4}中却不存在众数。
平凡算法:排序 + 扫描
但进一步的,若限制时间不超过O(n),附加空间不超过O(1)呢?
不难验证,若众数存在,那众数必然为中位数。
同样的,只要能够找出中位数,我们就可以在线性时间内验证它是否是众数。
我们只需要遍历一趟数据集,再统计出目标元素的个数,即可验证。
但是这个目标很难实现,所以我们需要找到一个更弱的,更容易实现的必要条件。
我们想以某种安全的方式缩小问题的规模,将在A中寻找众数的问题变为在A-P中寻找众数的问题。
若在向量A的前缀P(P为偶数)中,元素x出现的次数恰占一半,则A有众数仅当,对应的后缀A - P有众数m,且m就是A的众数。
既然最终总要花费O(n)的时间通过一次线性扫描来确定候选者是否为众数。所以我们只需要考虑A的确含有众数m的情况。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。