分配排序和归并排序

10·5  分配排序

 

10·5·1  分配排序概述

1、         分配排序的实例

（1）扑克牌的排序

扑克牌有花色和面值（点数）。规定花色高于面值。在花色中规定梅花>方块>红心>黑桃；在面值中2<3<4<…<10。其排序有两种方法：

方法1：先按花色分成4堆，每堆内按面值从小到大排序，最后按花色顺序收集起来。这种方法叫最高位（MSD）优先法。

方法2：先按面值分成13堆，将13堆从小到大排序，再按花色分成4堆，最后按花色顺序收集起来。这种方法叫最低位（LSD）优先法。

（2）卡片的排序

卡片按日期（年月日）建立，然后以建立日期为关键字进行排序。

方法1：先按年份分堆，同年的卡片按月份分堆，同月的卡片按日分堆，最后顺序收集这些卡片。这种方法叫最高位（MSD）优先法。

方法2：先按日分堆并收集，再按月份分堆并收集，最后按年分堆并收集。这种方法叫最低位（LSD）优先法。

2、分配排序的方法

最高位（MSD）优先法是按最高位分成若干子集，子集再分成子集，在各子集中排序，最后收集；最低位（LSD）优先法是从最低位开始到最高位结束，进行若干次分配和收集。

    当关键字为一个字段时，亦可使用分配排序方法。如000---999。

10·5·2  基数排序

    将最低位优先法用于单关键字的情况。

1、         基数排序的基本思想

n个记录的关键字进行排序，每个关键字看成是一个d元组：

k_i=(k_i^1, k_i²,..., k_i^d)

其中

c₀<=k_i^j <=c_r-1   ( 1<=i<=n,  1<=j<=d )

排序时先按k_i^d 的值，从小到大将记录分到r（称为基数）个盒子中，再依次收集；然后按k_i^d-1的值再这样作。直至按k_i¹分配和收集序列为止，排序结束。

在关键字为数字时，r=10,  0<=c_i<=9， 1<=i<=d；

在关键字为字母时  r=26,  ’A’<=c_i<=’Z’,  1<=i<=d。

2、         基数排序的实例模拟

   设待排序文件各记录的关键字为288，371，260，531，287，235，56，299，18，23。这时 r=10, d=3。进行3趟分配和3趟收集。

基数排序可以采用顺序存储方式。使用R数组存放待排序记录，用r个数组存放分配时的r个队列。分配一次和收集一次都需要n次移动，d遍分配和收集，共需2dn移动。每个队列最大为n，共需rn个结点。

若采用链式存储方式，在R数组中，每个记录设一个next字段，存放下一结点的下标（静态链表）。记录的移动次数降为0，辅助空间为O(n+r)，分配时间O(n)，收集时间O(n)，时间复杂度O(d(n+r))。

3、         基数排序的算法

  首先定义新的数据类型：

  chtype=c1..crd;

  struct node{

   chtype  key[1..d];

anytype otheritem;

int next;

   }R[n+1]

(1)         [初始化]

for (i=0;i  R[i].next=i+1;

R[n].next=0;

(2)         [准备] p=1;  /* 指向静态链表中第一个元素 */

(3)         [排序]

while (i=d;i>0;i--)

{ ① [给Q初始化]

循环 j=c₀,c₁,…,c_n-1,执行

  Q[j].f=0; Q[j].e=0  /* 队头、队尾指针为0 */

② [分配] 循环反复执行下列语句，直至p=0

(a)         k=R[p].key[i]  /* 取关键字的第i个字符 */

  (b) IF Q[k].f=0 THEN Q[k].f=p ELSE R[Q[k].e].next=p

  (c) Q[k].e=p       /* 修改队头队尾指针 */

  (d) p=Q[p].next;   /* 取关键字的下一个字符 */

③ [收集]

(a) j=c₀

(b)         循环 当Q[j].f=0时，反复执行

j=succ(j)

(c)         p=Q[j].f;  t=Q[j].e 

(d)         循环 k=succ(j),…,c_r-1,执行

若Q[k].f<>0,则R[t].next=Q[k].f; t=Q[k].e

         (e) R[t].next=0       /* 静态链表尾 */

(4)         [算法结束]

3·6  归并排序

1、         归并排序的基本思想

   设待排序文件有n个记录，开始首先假定这n个记录都是有序的（这是自然的，一个记录当然自己有序）。然后进行归并，将相邻的有序子文件合并成一个较大子文件，如此下去，直至整个文件有序。对于二路归并来说，第一次长1的有序子文件两两归并得到长为2的é ù个有序子文件，再两两归并得到长为4的é ù个有序子文件，如此下去，直至得到长为n的有序文件。

2、         二路归并排序的算法

（1）    两个有序子文件归并成一个有序子文件

 merge(r,r1,low,mid,high)

 /*r[low]到r[mid]与r[mid+1]到r[high]是两个有序子文件* /

/* 本算法将其归并成一个有序子文件从r1[low]到r1[high]*/

rectype r[],r1[];

int low,mid,high;

{ int i=low; j=mid+1; k=low;

  while  ((i<=mid) && (j<=high))

    if (r[i].key<=r[j].key r1[k++]=r[i++]; /*取小者复制*/

    else r1[k+=]=r[j++];

while  (i<=mid)  r1[k++]=r[i++];/*复制第一个文件剩余记录*/

while (j<=high)  r1[k++]=r[j++];/*复制第二个文件剩余记录*/

}

（2）    一趟归并的算法

mergepass(r,r1,length)

/*对r进行一趟归并，结果放在r1中 */

rectype r[],r1[];

int length;          /* length是本趟归并的有序子文件的长度*/

{int i=0,j;          /*指向第一对子文件起始点 */

 while (i+2*length<=n)

  {merge(r,r1,i,i+length-1,i+2*length-1)

   i=i+2*length    /*指向下一对子文件起始点 */

  }

 if (i+leng-1  /* 剩下两个子文件，其中一个长度小于length*/

    merge(r,r1,i,i+length-1,n-1);

 else      /* 子文件个数为奇数，将最后一个子文件复制到r1中*/

    for (j=i;j

}

（3）    二路归并排序的算法

mergesort( r )

rectype r[];

{ int length=1;

  while (length

   { mergepass(r,r1,length)   /* 一趟归并，结果在r1中 */;

length=2*length;

mergepass(r1,r,length)   /* 再次归并，结果在r中 */;

lenth=2*length;

   }

}

3、         二路归并排序的时间复杂度

   第i趟排序后，有序子文件长度为2ⁱ，具有n个记录的文件排序，必须做「log₂ⁿù趟归并，每趟所花时间为O（n），故二路归并排序的时间复杂度为O（nlog₂ⁿ），所需空间为O（n）。