排序（二）键索引、桶排序、位示图、败者树等

排序（二）

以上排序算法都有一个性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们把这类排序算法称为比较排序。

任何比较排序的时间复杂度的下界是nlgn。

以下排序算法是用运算而不是比较来确定排序顺序的。因此下界nlgn对它们是不适用的。

键索引计数法（计数排序）

计数排序假设n个输入元素中的每一个都是在0到k区间的一个整数，其中k为某个整数。

思想：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置了。

例如：

学生被分为若干组，标号为1,、2、3、4等，在某些情况下我们希望将全班同学按组序号排序分类。

1.频率统计：< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPrXa0ruyvb7NysfKudPDaW50yv3X6WNvdXRbXbzGy+PDv7j2vPyz9s/WtcTGtcLKoaM8L3A+CjxwPrbU09rK/dfp1tC1xMO/uPbUqsvYo6y2vMq508PL/LXEvPy3w87KY291bnRbXdbQtcTP4NOm1KrL2LKivavG5LzTMaGjo6i8tLDRvPwmIzIwNTQwO9f3zqpjb3V0W121xMv30v2jqcjnufu8/CYjMjA1NDA7zqpyo6zU8r2rY291bnRbciYjNDM7MV280zEuo6jOqsqyw7TQ6NKqvNMxo7/J1LrzveLKzaOpPC9wPgo8cD4gPC9wPgo8cD5mb3IgKGk9MDsgaTxOOyBpJiM0MzsmIzQzOyk8L3A+CjxwPiAgIGNvdW50W2FbaV0ua2V5KCkmIzQzOzFdJiM0MzsmIzQzOyA7PC9wPgo8cD5jb3VudFswfjVdo7owIDAgMyA1IDYgNjwvcD4KPHA+IDwvcD4KPHA+Mi69q8a1wsrXqru7zqrL99L9o7o8L3A+CjxwPjxicj4KPC9wPgo8cD6908/CwLSjrM7Sw8e74cq508Njb3VudFtdwLS8xsvjw7+49rz81NrFxdDyveG5+9bQtcTG8Mq8y/fS/c671sOho9Ta1eK49sq+wP3W0KOs0vLOqrXa0rvX6dbQ09AzuPbIy6Ostdq2/tfp1tDT0DW49sjLo6zS8rTLtdrI/dfp1tC1xM2s0afU2sXF0PK94bn7yv3X6dbQtcTG8Mq8zrvWw86qOKGjPC9wPgo8cD621NPaw7+49rz8JiMyMDU0MDtyo6zQodPaciYjNDM7MbXEvPy1xMa1wsrWrrrNzqrQodPacrXEvPy1xMa1wsrWrrrNvNPJz2NvdW50W3Jdo6zS8rTLtNPX88/y09K9q2NvdW50W13XqruvzqrSu9XF08PT2sXF0PK1xMv30v2x7crHutzI3dLXtcShozwvcD4KPHA+IDwvcD4KPHA+Zm9yIChpbnQgcj0wOyByPFI7IHImIzQzOyYjNDM7KTwvcD4KPHA+ICAgY291bnRbciYjNDM7MV0gJiM0Mzs9IGNvdW50W3JdIDs8L3A+CjxwPmNvdW50WzB+NV2jujAgMCAzIDggMTQgMjA8L3A+CjxwPiA8L3A+CjxwPjMuIMr9vt231sDgo7o8L3A+CjxwPjxicj4KPC9wPgo8cD7U2r2rY291bnRbXcr91+nXqru7zqrSu9XFy/fS/bHt1q6686OsvavL+dPQ1KrL2KOo0afJ+qOpPHN0cm9uZz7Sxravtb3Su7j2uKjW+sr91+lhdXhbXdbQ0tS9+NDQxcXQ8jwvc3Ryb25nPqGjw7+49tSqy9jU2mF1eFtd1tC1xM671sPKx9PJy/y1xLz8o6jX6bHwo6m21NOmtcRjb3VudFtdJiMyMDU0MDu+9raotcSjrNTa0sa2r9auuvO9q2NvdW50W13W0LbU06bUqsvYtcQmIzIwNTQwO7zTMaOs0tSxo9akY291bnRbcl3X3MrHz8LSu7j2vPzOqnK1xNSqy9jU2mF1eFtd1tC1xMv30v3Ou9bDoaM8c3Ryb25nPtXiuPa5/bPM1rvQ6LHpwPrSu7Hpyv2+3by0v8my+sn6xcXQ8r3hufs8L3N0cm9uZz6hozwvcD4KPHA+o6jV4tbWyrXP1re9yr21xM7ItqjQ1MrHuty52Lz8tcShqqGqvPzP4M2stcTUqsvY1NrFxdDyuvO74bG7vtu8r7W90rvG8KOstavP4LbUy7PQ8sO709Cx5LuvoaOjqTwvcD4KPHA+Zm9yIChpbnQgaT0wOyBpPE47IGkmIzQzOyYjNDM7KTwvcD4KPHA+ICAgYXV4W2NvdW50W2FbaV0ua2V5KCldJiM0MzsmIzQzO10gPSBhW2ldIDs8L3A+CjxwPiA8L3A+CjxwPjQuILvY0LSjujwvcD4KPHA+PGJyPgo8L3A+CjxwPtLytMvO0sPH1Nq9q9Sqy9jSxravtb24qNb6yv3X6bXEuf2zzNbQzeqzycHLxcXQ8qOsy/nS1NfuuvPSu7K9vs3Kx72rxcXQ8rXEveG5+7i01sa72NStyv3X6dbQoaM8L3A+CjxwPmZvciAoaW50IGk9MDsgaTxOOyBpJiM0MzsmIzQzOyk8L3A+CjxwPiAgIGFbaV0gPSBhdXhbaV0gOzwvcD4KPHA+IDwvcD4KPHA+zNi146O6vPzL99L9vMbK/beoysfSu9bWttTT2jxzdHJvbmc+0KHV+8r9vPzFxdDyPC9zdHJvbmc+t8ezo9PQ0KfItLOjs6Oxu7r2wtS1xMXF0PK3vbeooaM8L3A+CjxwPrz8y/fS/bzGyv23qLK70OjSqrHIvc+jrNa70qq1sbe2zqdS1NpOtcTSu7j2s6PK/dLy19O3ts6n1q7E2qOsy/y2vMrH0ru49s/f0NTKsbzkvLax8LXExcXQ8re9t6ihozwvcD4KPHA+IDwvcD4KPHA+IDwvcD4KPGgyPrv5yv3FxdDyPC9oMj4KPHA+PGJyPgo8L3A+CjxwPtPQyrG68qOsztLDx9Do0qq21LOktsi2vM/gzay1xNfWt/u0rr340NDFxdDyoaPV4tbWx+m/9tTaxcXQ8tOm08PW0Lrcs6O8+6GqoaqxyMjntee7sLrFwuuhotL40NDVy7rFoaJJULXY1re1yLa8yse15NDNtcS2qLOk19a3+7SuoaM8L3A+CjxwPr2rtMvA4NfWt/u0rsXF0PK/ydLUzai5/TxzdHJvbmc+tc3Ou9PFz8i1xNfWt/u0rsXF0PI8L3N0cm9uZz7AtM3qs8mho8jnufvX1rf7tK61xLOktsi++c6qV6OsxMe+zTx1PrTT09LP8tfz0tTDv7j2zrvWw7XE19a3+9f3zqq8/DwvdT6jrNPDvPzL99L9vMbK/beoo6i78rLlyOvFxdDyo6m9q9fWt/u0rsXF0PJXsemhozwvcD4KPHA+o6jOqsHLyLexo7v5yv3FxdDytcTV/ci30NSjrNK7zrvK/cXF0PLL47eosdjQ68rHzsi2qLXEoaPA/cjno7q8xsr9xcXQ8qGisuXI68XF0PKjqTwvcD4KPHA+IDwvcD4KPHA+zNi146O6u/nK/cXF0PLKx7fxsci7+dPasci9z7XExcXQ8svjt6ijqMjnv+zL2cXF0PKjqbj8usPE2KO/PC9wPgo8cD67+cr9xcXQ8rXEyrG85Li01NO2yM6qz9/Q1Ly2o6huo6mjrNXi0ru94bn7v7TJz8il0qqxyL/sy9nFxdDytcTG2s371MvQ0MqxvOS0+rzbo6hubGduo6m4/LrD0rvQqaGjPHU+tavKxzwvdT6jrNTa1eLBvbj2se2078q91tDS/rqs1Nqxs7rztcSzo8r9z+7S8tfTyseyu82stcShozwvcD4KPHA+1Nq0psDttcRuuPa52Lz819bKsaOsvqG53Lv5yv3FxdDy1rTQ0LXE0a27t8LWyv274bHIv+zL2cXF0PLSqsnZo6y1q8O/0rvC1sv8y/m6xLfRtcTKsbzk0qqzpLXDtuCho8fSv+zL2cXF0PLNqLOjv8nS1LHIu/nK/cXF0PK4/NPQ0Ke12Mq508PTsrz+tcS7urTmoaM8L3A+CjxwPrTLzeKjrMD708O8xsr9xcXQ8tf3zqrW0Lzkzsi2qMXF0PK1xLv5yv3FxdDysrvKx9St1rfFxdDyo6y2+LrctuBubGduyrG85LXEsci9z8XF0PLKx9St1rfFxdDyoaPS8rTLo6y1sdb3tOa1xMjdwb+xyL3Psaa588qxo6zO0sPHv8nE3LvhuPzH48/y09rP8b/sy9nFxdDy1eLR+bXE1K3Wt8XF0PKhozwvcD4KPHA+IDwvcD4KPHA+IDwvcD4KPGgyPs2wxcXQ8jwvaDI+CjxwPjxicj4KPC9wPgo8cD7NsMXF0PKjqGJ1Y2tldCBzb3J0o6m82cnoyuTI68r9vt23/rTTvvnUyLfWsryjrMbktsDBorfWsrzU2lswLE2jqcf4vOTJz6Gjxr2++cfpv/bPwsv8tcTKsbzktPq8286qTyhuKaGjPC9wPgo8cD7LvM/ro7rNsMXF0PK9q1swLE2jqcf4vOS7rrfWzqpuuPbP4M2stPPQobXE19PH+Lzko6y78rPGzqo8c3Ryb25nPs2wPC9zdHJvbmc+oaM8L3A+CjxwPsi7uvOjrL2rbrj2yuTI68r9t9ax8LfFtb2497j2zbDW0KGj0vLOqsrkyOvK/b7dyrG++dTIoaK2wMGitdi31rK81NpbMCxNo6nH+Lzkyc+jrMv50tTSu7Djsru74bP2z9a63Lbgyv3C5NTazazSu7j2zbDW0LXEx+m/9qGjzqrBy7XDtb3K5LP2veG5+6OsztLDx8/IttTDv7j2zbDW0LXEyv29+NDQxcXQ8qOsyLu687HpwPrDv7j2zbCjrLC01dW0ztDysNG497j2zbDW0LXE1KrL2MHQs/bAtLy0v8mhozwvcD4KPHA+o6jNsMa9xcXQ8svjt6i7udDo0qrSu7j2wdnKscr91+lCWzAuLm4tMV3AtLTmt8XBtLHto6i8tM2wo6mjrLKivNnJ6LTm1NrSu9bW08PT2s6su6TV4tCpwbSx7bXEu/rWxqOpPC9wPgo8cD6jqNPQtePP8bn+z6Ox7bXEwK3BtLeotcS0psDtt73KvaGjo6k8L3A+Cjxicj4KPHA+PGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_yzr7f__.jpg" alt="\">

位示图

思想：用比特位的相对位置(索引)来表示一个数值。

即就像用数组的下标来表示一个数值那样，只不过为了节省内存我们用一个bit的位置来标记一个数。

例如：我们可以将集合{1, 2, 3, 5,8, 13}存储在下面这个字符串中：0 1 1 1 0 10 0 1 0 0 0 0 1 0 0 0 0 0 0 集合中代表数字的各个位设置为1，而其他的位全部都设为0。

特点：位示图法适用的问题是（该情况在排序问题中不太常见）：

输入的范围相对要小些，并且还不包含重复数据，且没有数据与记录相关联。

【应用举例】

考虑这样一个问题：给一个磁盘文件排序。（具体描述如下）

输入：

所输入的是一个文件，至多包含n个不重复的正整数，每个正整数都要小于n，这里n=10^7. 这些整数没有与之对应的记录相关联。（即仅对这些整数排序）

输出：

以增序形式输出经过排序的整数列表。

约束：

至多只有1MB的可用主存，但是可用磁盘空间非常充足。10秒钟是最适宜的运行时间。

看到磁盘文件排序，我们首先想到经典的多路归并排序。（后面会讲到）

一个整数为32位，我们可以在1MB空间中存储250000个数。因此，我们将使用一个在输入文件中带有40个通道的程序。在第一个通道中它将249999之间的任意整数读到内存中，并（至多）对250000个整数进行排序，然后将它们写到输出文件中。第二个通道对250000到499999之间的整数进行排序，依此类推，直到第40个通道，它将排序9750000到9999999之间的整数。在内存中，我们用快速排序，然后把排序的有序序列进行归并，最终得到整体有序。

但是，此方式的效率较低，光是读取输入文件就需要40次，还有外部归并的IO开销。

怎样降低IO操作的次数，来提高程序的效率？一次把这一千万个数字全部读入内存？

用位图的方式，我们将使用一个具有一千万个bit位来表示该文件，在该bit位串中，当且仅当整数i在该文件中时，第i位才打开(设为1)。

给定了表示文件中整数集合的位图数据结构后，我们可以将编写该程序的过程分为三个自然阶段，第一个阶段关闭所有的位，将集合初始化为空集。第二个阶段读取文件中的每个整数，并打开相应的位，建立该集合。第三个阶段检查每个位，如果某个位是1，就写出相应的整数，从而创建已排序的输出文件。

内部排序方法总结

稳定性

如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。

这个性质在许多情况下很重要。

（例如：

考虑一个需要处理大量含有地理位置和时间戳的事件的互联网商业程序。

首先，我们在事件发生时将它们挨个存储在一个数组中，这样在数组中它们已经是按时间排序好了的。现在再按照地理位置切分，如果排序算法不是稳定的，排序后的每个城市的交易可能不会再是按照时间顺序排序的了。

）

算法 是否稳定

选择排序 否

插入排序 是

希尔排序 否

快速排序 否

三向快速排序 否

归并排序 是

堆排序 否

键索引计数 是

基数排序 是

快速排序是最快的通用排序算法。

快速排序之所以快是因为它的内循环中的指令很少（而且它还能利用缓存，因为它总是顺序地访问数据），所以它的运行时间的增长数量级为~cNlgN，而这里的c比其他线性对数级别的排序算法的相应常数都要小。

且，在使用三向切分之后，快速排序对于实际应用中可能出现的某些分布的输入变成线性级别的了，而其他的排序算法仍然需要线性对数时间。

如果稳定性很重要而空间又不是问题，归并排序可能是最好的。

----------------------------------------------------------------------外部排序---------------------------------------------------------------------

（我们为什么要进行外部排序？为什么不在插入数据时就按照某种数据结构组织，方便查找且有序。这就像静态查找树那样，没什么实用功能）

外部排序基本上由两个相对独立的阶段组成。

首先，按可用内存大小，将外存上含有n个记录的文件分成若干长度为l的子文件，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段。

然后，对这些归并段进行逐趟归并，使归并段逐渐由小至大，直到得到整个有序文件为止。

每一趟归并从m个归并段得到m/2个归并段。这种归并方法称为2-路平衡归并。

若对上例中所得的10个初始归并段进行5-路平衡归并，则从下图可见，仅需进行二趟归并，外排时总的IO读/写次数显著减少。

一般情况下，对m个初始归并段进行k-路平衡归并时，归并的趟数s = log_km

可见，若增加k或减少m便能减少s。

一般的归并merge，每得到归并后的有序段中的一个记录，都要进行k-1次比较。显然，为得到含u个记录的归并段需进行(u-1)(k-1)次比较。

内部归并过程中总的比较次数为：

log_km (k-1) (u-1)t_mg =( log₂m/ log₂k)(k-1) (u-1)t_mg

所以，要单纯地增加k将导致内部归并的时间，这将抵消由于增大k而减少外存信息读写时间所得效益。

然而，若在进行k-路归并时利用败者树（Tree of Loser），则可使在k个记录中选出关键字最小的记录时仅需进行log₂k次比较。则总的归并时间变为log₂m (u-1)t_mg此式与k无关，它不再随k的增长而增长。

败者树

它是树形选择排序的一种变型。每个非终端结点均表示其左、右孩子结点中的“败者”。而让胜者去参加更高一层的比赛，便可得到一颗“败者树”（所谓“胜者”就是你想选出来的元素）。

以一颗实现5-路(k=5)归并的败者树为例：

数组ls[0…k-1]表示败者树中的非终端结点。败者树中根结点ls[1]的双亲结点ls[0]为“冠军”，其他结点记录的是其左右子树中的“败者”的索引值。b[0…k-1]是待比较的各路归并序列的首元素。

ls[]中除首元素外，其他元素表示为完全二叉树。

那表示叶子结点的b[]该如何与之对应？

叶结点b[x]的父结点是ls[(x+k)/2]。

败者树的建立：

1、 初始化败者树：把ls[0..k-1]中全设置为MINKEY（可能的最小值，即“绝对的胜者”）

//我们设一个b[k]= MINKEY，ls[]中记录的是b数组中的索引值。故初始为5.

2、从各叶子结点溯流而上，调整败者树中的值。

拿胜者s(初始为叶结点值)与其父结点中值比较，谁败(较大的)谁上位(留着父结点中)，胜者被记录在s中。（决出胜者，记录败者，胜者向上走）

//对于叶结点b[4]，调整的结果如下：

//对于叶结点b[3]，调整的结果如下

//同理，对于叶结点b[2]，调整的结果如下

//同理，对于叶结点b[1]，调整的结果如下

//同理，对于叶结点b[0]，调整的结果如下

void CreateLoserTree(LoserTree &ls)
{
    b[k].key = MINKEY ;

    //设置ls中“败者”的初值
    for (i=0; i
  
   =0; --i)
        Adjust(ls, i) ;
}

void Adjust(LoserTree &ls, int m)
{
    //沿从叶节点b[m]到根结点ls[0]的路径 调整败者树
    for (i = (m + k)/2; i>0; i=i/2)  //ls[i]是b[m]的双亲结点
    {
        if (b[m].key > b[ls[i]].key) 
            exch(m, ls[i]) ;         //m保存新的胜者的索引
    }
    ls[0] = m ;
}

  

【后记】

从n个数中选出最小的，我们为什么要用败者树？

首先，我们想到用优先队列，但其应对这种多路归并的情况，效率并不高。

堆结构：其待处理的元素都在树结点中(在叶节点和非叶子节点中)

败者树：其待处理的元素都在树的叶子结点上，其非叶子结点上记录上次其子结点比较的结果。

这样的话，堆结构的某个叶子结点不是对应固定的某个待归并序列。一次选出最值之后，还得取出各归并序列的首元素，重建堆再调整，不能利用之前比较的结果。

而败者树，一个叶结点固定地对应一个归并序列，这样，若其序列的首元素被选出，则序列的下个元素可以直接增补进入结点，然后沿树的路径向上比较。

总结：堆结构适用于插入是无规则的，选出最值。

败者树适用于多路序列的插入，选出最值。