Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3881802
  • 博文数量: 408
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9820
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2022年(1)

2021年(1)

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-04-21 21:25:50

一.归并排序
  归并排序 (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位的十进制非负整数,从最高位到最低位(个位)的编号依次为12d。设置10个队列(即上面所说的桶),它们的编号分别为0129。当第一遍扫描时,将记录按关键字的最低位(即第d位)数分别放到相应的队列中:最低位数为0的关键字,其记录依次放入0号队列中,最低位数为1的关键字,其记录放入1号队列中;最低位数为9的关键字,其记录放入9号队列中。这一过程叫做第一趟分配(按最低位数分配)。现在把这10个队列中的记录,按0号,1号,9号队列的顺序收集和排列起来,同一队列中的记录按先进先出的次序排列。这是第一趟基数排序。第二趟排序使用同样的办法,将第一趟排序后的记录按其关键字的次低位数(第d-1位)分配到相应的队列中,再把队列中的记录收集和排列起来。如此重复进行。第d趟排序时,按第d-1趟排序后记录的关键字的最高位(第1位)进行分配,再收集和排列各队列中的记录,即得到了初始序列的有序序列,

 

阅读(1575) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~