归并排序与基数排序

一．归并排序
　　归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

归并排序的步骤如下：

1.      Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。

2.      Conquer: 对这两个子序列分别采用归并排序。

3.      Combine: 将两个排序好的子序列合并成一个最终的排序序列。

在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。

 

1.两路归并排序算法思路
①把 n 个记录看成 n 个长度为 l 的有序子表；
②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；
③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
【例】 有一组关键字 {4,7,5,3,2,8,6,1},n=8, 将其按由小到大的顺序排序。 两路归并排序操作过程如图 9.12 所示，其中 l 为子表长度。

初始：      [4]   [7]   [5]   [3]  [2]  [8]  [6]  [1]  i=1

第1趟：    [4    7]   [5     3]  [2   8]  [6   1]  i=2

第2趟：    [4    7    5     3]  [2   8    6   1]  i=4

第3趟：    [4    7    5     3   2   8    6   1]  i=n

 

2.算法实现
　　此算法的实现不像图示那样简单，现分三步来讨论。首先从宏观上分析，首先让子表表长 L=1 进行处理；不断地使 L=2*L ，进行子表处理，直到 L>=n 为止，把这一过程写成一个主体框架函数 mergesort 。然后对于某确定的子表表长 L ，将 n 个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数 mergepass ，可由 mergesort 调用。最后再看每一组（一对）子表的归并，其原理是相同的，只是子表表长不同，换句话说，是子表的首记录号与尾记录号不同，把这个归并操作作为核心算法写成函数 merge ，由 mergepass 来调用。
3.具体算法
template
  void merge( T r[],T r2[],int s,int mid,int t)
  //s为第一个子表首元素的下标，mid为第一个子表末元素的下标
  //t为第二个子表末元素的下标
   { int i,j,k;
     i=s;j=mid+1;k=s-1;   //k是r2的初始指针
     while((i<=mid)&&(j<=t))
       { k=k+1;
         if(r[i].key<=r[j].key){r2[k]=r[i];i++;}
         else{r2[k]=r[j];j++;}
       }
     while(i<=mid){k++;r2[k]=r[i];i++;}
     while(j<=t){k++;r2[k]=r[j];j++;}
  }   //merge
3.算法分析
（1）稳定性
     　归并排序是一种稳定的排序。
（2）存储结构要求
    　可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
    　对长度为n的文件，需进行  趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
   　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
  注意：
    　若用单链表做存储结构，很容易给出就地的归并排序。

二．基 数 排 序

前面介绍的排序方法都是根据关键字值的大小来进行排序的，实现排序主要是通过比较和移动记录这两种操作。

本节介绍的方法不需要进行记录关键字间的比较，是按组成关键字的各个位的值来实现排序的，这种方法称为基数排序（Radix Sorting）。基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。采用基数排序法需要使用一批桶（或箱子）故这种方法又称为桶排序。

此方法一般仅是用于记录的关键字为整数类型的情况。

假定待排序列中所有记录的关键字为不超过d位的十进制非负整数，从最高位到最低位（个位）的编号依次为1，2，…，d。设置10个队列（即上面所说的桶），它们的编号分别为0，1，2，…，9。当第一遍扫描时，将记录按关键字的最低位（即第d位）数分别放到相应的队列中：最低位数为0的关键字，其记录依次放入0号队列中，最低位数为1的关键字，其记录放入1号队列中…；最低位数为9的关键字，其记录放入9号队列中。这一过程叫做第一趟分配（按最低位数分配）。现在把这10个队列中的记录，按0号，1号，9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。这是第一趟基数排序。第二趟排序使用同样的办法，将第一趟排序后的记录按其关键字的次低位数（第d-1位）分配到相应的队列中，再把队列中的记录收集和排列起来。如此重复进行。第d趟排序时，按第d-1趟排序后记录的关键字的最高位（第1位）进行分配，再收集和排列各队列中的记录，即得到了初始序列的有序序列，