算法之排序:第二节

1、堆排序(胜者树)
2、败者树
3、桶排序
4、计数排序
5、基数排序

本节对上述排序算法进行分析。

堆排序(胜者树)

堆排序是一种不稳定的原地排序算法(in place),其与上一节说到的排序算法稍有不同的是,其借助了二叉树这个结构体来完成排序。同时,其又类似冒泡、选择排序,是一种最值排序,即排序是该算法的副产品,其核心大于找最值。这也是为什么该算法还被应用于最优队列(priority quueu)的原因 。由于使用了非线性结构体(逻辑二叉树、实则仍需要借助线性存储结构),使其找最值的过程从冒泡、选择排序的O(n),变为O(lg(n))。其Pesudocode(ascend version):
HEAP-SORT(A,i,j) # [i,j]

  1. BUILD-HEAP(A,i,j)
  2. for n from 0 to j-i
  3.     A[i] <-> A[j-n]
  4.     HEAPFY(A,i,j-n-1)

上面这段代码中的BUILD-HEAP为将一个指定线性存储结构中的指定区域数据,调整为一个有序堆。而有序堆的定义为:堆自身及任意子堆需满足(以大顶堆为例)

定义1:{A | ROOT(A) >=CHILD_ELEMENT(A)}

其中ROOT(A)表示堆的根元素,CHILD_ELEMENT(A)表示堆中除根元素外的任意其它元素。转换为线性存储结构中描述为:

定义2:  {(A,i)  | A[i*2] <= A[i] && A[i*2+1] <=A[i], i ∈[1,SIZE(A)/2]}

其中SIZE(A)表示堆A中的有效元素个数,其中i的取值范围为堆中的内点索引范围,内点是指在堆中有子结点的结点。那为什么说SIZE(A)/2就是索引号最大的内点呢?因为堆每增加2个结点,内点最大索引数加1,这里用数学中的归纳法来证明:

  1. n=0时,堆中无结点,那么最大内点为 n/2 为0,结论成立
  2. 堆为n,最大内点索引为k,即k=n/2
  3. 堆增加2个结点,即为n+2,最大内点索引为 (n+2)/2=n/2+1=k+1,结论成立

同时,也说明在二叉树中内点数与叶子树数相等或差1(总数为奇数时差1、总数为偶数时相等)。

BUILD-HEAP的算法依据正是来自定义2,即需要对堆中的内点调整以保持一种“有序”的状态,其伪代码为:BUILD-HEAP(A,i,j) # [i,j]

  1. k = (j-i+1)/2
  2. APPEND(A,0)           # add an element,to smooth algorithm
  3. t = A[j+1]
  4. A[j+1] <- INT_MIN    # set sentinel
  5. for n from k to 1
  6.     m = INDEX(MAX(A[n],A[2n],A[2n+1])
  7.     A[n] <-> A[m]
  8. A[j+1] <- t
  9. POP(A)

HEAPFY的算法,同样来自定义2,即当整个堆的根元素发生变化时,需要立即调整堆,以保持堆的定义,其伪代码为:HEAPFY(A,i,j):

  1. if j>=i
  2.     return
  3. n <- INDEX(MAX(A[i],A[i/2],A[i/2+1]))
  4. if n == i
  5.     return
  6. A[i] <-> A[n]
  7. HEAPFY(A,n,j)

通过上述伪代码,可以看得出HEAPFY是一个递归算法,由于其为尾递归,因此即便可以转化为循环体,那么其思路同样是一种递归思路:破坏子堆秩序,调整子堆。

堆排序首次在排序算法中利用特殊的数据结构来完成算法。

堆排序(败者树)

败者树源自对堆排序的改造,其适合多路外部排序。先尝试着从信息论的角度去解释败者树算法原理。借助堆排序的信息结构,即二叉树对数据集大小关系描述。假设要对n路(链表或线性表)数据进行排序,那么理论上我们用n个元素(有序索引)就可以描述n路数据首结点的大小关系(决策树比较模型)。因此,每从数据中取出一个最值后,只需要再调整这个有序索引,就可以再次表征新n路数据的首结点大小关系。但如果采用胜者树,即有序索引记录子树胜出的结点索引,这样肯定会存在重复存储的情况:作为两棵子树胜出者,即很有可能在上层的比较中胜出,这样这个结点就占用了两个索引位置。换一个思路,即索引结点记录败者(因为是二叉树,也就是次优),那么n个元素就能描述n个数据的大小关系。以上,就是败者树的算法原理。

败者树与胜者树(堆排序)相同,也存在树建立和树维持两个基本算法。其中败者树的维持伪码为:
KEEPFTREE(A,D,n,i) # A:索引 D:外部数据 n:n路外部数据 i:第i路的数据更新,需要调整

  1. parent_index <- (i+n)/2    # i+n表示完整二叉树的数量,i为内点数量,n为叶子数据, 即外部数据
  2. successor_index <- i       # 假设新结点为最大
  3. while parent_index > 0
  4.     if D[parent_index] > D[successor_index]  # 新后结点不是最大
  5.          A[parent_index] <-> succesor_index # 互换,新的作为败者留下,原来的作为胜者继续向上
  6.     parent_index = parent_index/2
  7. A[0] <- successor_index   #最终的胜者记录在0处,并不是败者树(完整二叉树)结点

败者树建立体现了算法实现中的一种思维方式:要初始化和实现一种秩序,那么先将全部元素设置为反向状态,以此来实现全元素的重新“洗牌”。因为败者树中的结点(完整二叉树中的内点)记录的都是叶子结点的“败者”,即除最大值元素外,其它元素的索引。因此,我们一开始让所以的败者树结点全部指向胜者的结点。然后依次将所有数据结点加入,即利用上面的KEEPFTREE就可以实现败者树结点的初始化。实际上我们一开始并不知道n路数据中哪一个路的首结点最大,因此可以先伪造一个,让其绝对最大。因此BUILDFTREE(A,D,n)的伪码如下:

  1. for i from 1 to n
  2.     A[i] <- n     # D[n]并不n路数据中元素,而伪造的最大值
  3. for i from 0 to n-1
  4.     KEEPFTREE(A,D,n,i) #从第0路数据,开始依次将数据加入败者树中索引起来

也许会奇怪,那BUILDFTREE结束后,伪结点怎么不在了,因为可以看出败者树在KEEPFTREE中,根本就不在乎胜者是谁,只是在最后一步将胜者索引放在一个0号位置存放起来。注意:这个位置并非败者树的一部分。又因为依次放入的n个结点都比伪结点小,因此整个败者树的索引结点肯定都会得到更新,而就在KEEPFTREE最后一步,将n个结点的胜者(真正胜者)更新到A[0],从而完成败者树的初始化。

前面讲到的排序都是基于元素间比较,即比较排序。下面从理论上来证明基于比较排序的理论时间复杂度,即无论你怎么优化,你的时间复杂度不会低于何值。这里采用《算法导论》里的决策树模型来分析:比较决策树

 

如上图所示,三个元素的比较,用决策树模型表示。可以看出,如果有n个元素,那么决策就会有n的阶乘个叶子,即n!。通过上图可以看出,由于比较过程中会出现在较短路径中即得出解,因此比较决策树不会是一棵满二叉树。而我们知道一颗满二叉树,叶子数k与树高度存在如下关系:

h = log2(k+1) + 1

如果说,有n!个元素的满二叉树的高度为 log2(n!+1)+1,由于上面的比较决策二叉树非满二叉树,因此其高度H > log2(n!+1) +1 > log2(n!) Θ nlog2(n),即基于比较的算法其下限为nlog2(n)。

下面来看一下,基于非比较的排序算法,一般而言这类算法都发生在特定的场景中,并非符合通用排序。

计数排序

其中计数排序就是利用了待排序集合中元素一种先验关系而实现元素排序,其先验关系为:

待排序元素为散列在整数区间S(包括负数)的整数,且 len(S)  Θ (n),即该区间跨度为固定常量

其算法本质,由于集合中元素大小范围是预知的,那么事先将排序空间构造好,然后直接将数映射到排序空间。借助计算的随机访问特性,可很好实现映射,但由于存在原集合中元素到排序空间中元素之间多对一的情况,因此需要算法对此进行特殊处理。如果没有这种多对一的情况,可以用《算法珠玑》中的位图排序来完成,其本质思想:同样是将排序空间构造好,映射原有集合。需要处理多对一情况的计数排序伪代码(假设元素都为正整数,若涉及负数区间,只要进行简单的移位即可)为:
COUNT_SORT(A,k,n):

  1. S[k]   # create count container
  2. for i from 1 to k
  3.     S[i] <- 0
  4. for i from 1 to n # n is len(A)
  5.     S[A[i]] = S[A[i]] + 1
  6. m <- 1
  7. for i from 1 to k
  8.     for j from 1 to S[i]
  9.         A[m++] <- i

上面这段伪码虽然最终在原地完成了排序,但计数排序还有另外一种理解。下面看看这段伪码:
COUNT_SORT(A,B,K):

  1. C[k]
  2. for i from 1 to k
  3.     C[i] <- 0
  4. for i from 1 to len(A)
  5.     C[A[i]] = C[A[i]] + 1
  6. for i from 2 to k # 这一步,完成计数排序中的计数部分,确定元素在排序集合中的“准确”位置
  7.     C[i] = C[i-1] + C[i]
  8. for i from 1 to len(A)
  9.     B[C[A[i]] <- A[i]
  10.     C[A[i]] = C[A[i]] -1

上面两段伪码,第一段伪码的“计数”主体为排序空间S中的离散元素,第二段伪码的“计数”主体为待排序集合中的离散元素。

基数排序

如果说计数排序对待排序集合有先验条件,那么基数排序与后面的桶排序基本可以说,只是对特定类型的集合进行排序,只能是从中汲取算法思想,很少会用来直接进行数据排序。基数排序来源于早期卡式计算机,Radix Sort中Radix(基)也是来源于卡片上的基(孔)。下面重点理解一下基数排序的算法思想,不进行伪码解释。基数排序:假设集合中每个元素都由相同的基(如数字中的个位、十位、、、),因此只要对基依次进行排序,就可以完成元素的排序。

桶排序

桶排序,其实也可以理解成HASH排序,即构造好直接或间接的有序空间,直接对待排序集合中元素进行HASH映射。然后,再对冲突元素进行内部排序,即可完成整体排序。这里说一下,《算法导论》的例子。

不管是在计数排序还是桶排序中,都需要考虑到计算机的空间复杂度,即有序空间构造的成本。因此,只有空间复杂度足够小,才能在计算机中实现这两个算法。因此,对于随机数集合K:

{x∈K | 0=<x<1},m=|K|

可以通过数学中常用到的空间转化,将集合中元素转化到一个固定大小(空间复杂度可接受)的空间中。即[0,n],转化关系为 ⌊n*x⌋,这样 ⌊n*x⌋ 就落在一个固定的空间[0,n),进行直接对元素进行bucket映射,当然肯定会有多个元素映射到同一个bucket中。但由于先验条件:随机数,因此每个bucekt中的元素个数也会是随机分布。再利用前面的基于比较的算法对bucket中的元素进行排序,然后将各个bucekt 串联起来就完成整个桶排序。

这样排序的算法复杂度为 \(\Theta (m+\sum_{i=1}^{n-1} n_{i}^2) = \Theta(m)\),其中 \( n_i\) 为第i个bucket中元素个数,其中推导过程摘自《算法导论》,这里进行定性分析,由于集合K中数据先验条件为随机生成,因此不会出现单个bucket有过多的元素聚焦,而出现排序复杂度为\( \Theta (m^2) \)

算法之排序:第二节》上有1条评论

发表评论