数据结构 第9章 排序

数据结构C++实现

所谓排序(Sorting)就是对数据元素集合建立某种有序排列的过程。排序在计算机软件系统设计中占有相当重要的地位，特别是在事务处理系统中，需要经常对有关的数据排序，以便提高检索等操作的效率。本章将介绍一些常用的排序算法，它们有：交换排序、插入排序、选择排序、归并排序和基数排序，并对有关的算法进行性能分析和对比。基础知识

1．排序：设含有n个数据元素的数据表为：{R[0]、R[1]、…、R[n-1]}，其相应的关键字序列为：{K[0]、K[1]、…、K[n—1]}。所谓排序，是确定0、1、…、n-1的一种排列p0、p1、…、pn-1，使各关键字满足如下的递增(或递减)关系：K[p0]≤K[p1]≤…≤K[pn—1]或K[p0]≥K[p1]≥…≥K[pn—1]2．排序的稳定性：如果在排序表中任意两个数据元素R[i]和R[j]（i≠j），它们的关键字K[i]＝K[j]，且在排序之前，数据元素R[i]排在R[j]的前面，如果在排序之后，数据元素R[i]仍在数据元素R[j]的前面，即不改变关键字相同的数据元素在排序前、后的相对位置，则称这种排序方法是稳定的，否则称这种排序方法是不稳定的。

3．内部排序与外部排序：根据在排序过程中数据元素是否全部在内存中进行，排序可分为两大类：内排序和外排序。内排序是指在排序过程中数据元素全部存放在内存进行的排序；外排序是指由于数据元素太多，在排序期间全部数据元素不能同时存放在内存中，必须在排序过程中，不断地在内存和外存之间交换数据元素的排序。

4．排序的效率：排序是经常使用的一种运算，因此，排序效率的高低普为人们注意，排序算法的效率可以从时间复杂度和空间复杂度两个方面来分析。排序算法的时间复杂度可用排序过程中的数据元素之关键字的比较次数与数据元素的移动次数来衡量。在本章下面各节讨论算法的时间复杂度时一般都按平均时间复杂度进行估算；对于那些受排序表中数据元素的初始排列及数据元素数目影响较大的算法，按最好情况和最坏情况进行分别估算。而算法的空间复杂度为算法执行时所需的附加存储空间。下面给出用顺序表表示的排序表的类定义:const

intMaxSize=100;template<classType>classsortlisttemplate<classType>classelement{//数据元素的类定义friend

classsortlist<Type>;private:Typekey;//数据元素的关键字

other;//其它信息public:element();//构造函数

TypegetKey(){returnkey;}//取数据元素关键字

voidsetKey(constTypek){key=k;}//修改数据元素关键字

element<Type>&operator=(element<Type>&x){this=x;}

intoperator==(Type&k){return!(key<k||k<key);}

intoperator!=(Type&k){return(key<k||k<key);}

intoperator<=(Type&k){return!(key>k);}

intoperator>=(Type&k){return!(key<k);}

intoperator<(Type&k){return(key<k);}

intoperator>(Type&k){return(key>k);}}template<classType>classsortlist{protected:element<Type>*Arr;//存储数据元素的向量（排序表）

intCurrentSize;//数据表中数据元素的个数public:sortlist():CurrentSize(0){Arr=newelement<Type>[MaxSize];}//构造函数

sortlist(){deleteArr[]};//析构函数

voidswap(element<Type>&x,element<Type>&y){element<Type>temp=x;x=y;y=temp;}//数据元素x和y交换位置}下面给出用链表表示的排序表的类定义:const

intMaxSize=100;template<classType>classsortlinklisttemplate<classType>classnode{//数据元素的类定义friend

classsortlinklist<Type>;private:Typekey;//数据元素的关键字

intnext;//后继指针

other;//其它信息public:node();//构造函数

TypegetKey(){returnkey;}//取数据元素关键字

voidsetKey(constTypek){key=k;}//修改数据元素关键字

intgetLink(){returnnext;}//取结点的后继指针

voidsetKey(const

intp){next=p;}//修改结点的后继指针

intoperator==(Type&k){return!(key<k||k<key);}

intoperator!=(Type&k){return(key<k||k<key);}

intoperator<=(Type&k){return!(key>k);}

intoperator>=(Type&k){return!(key<k);}

intoperator<(Type&k){return(key<k);}

intoperator>(Type&k){return(key>k);}}template<classType>classsortlinklist{protected:node<Type>*Arr;//存储排序表结点的向量（静态链表）

intCurrentSize;//排序表中的结点个数public:sortlinklist():CurrentSize(0){Arr=newnode<Type>[MaxSize];}//构造函数

sortlinklist(){deleteArr[]};//析构函数}

交换排序

交换排序的基本思想是对排序表中所有两两相邻的数据元素的关键字进行比较，如果发生逆序(即排列顺序与排序后的次序正好相反)，则两者交换位置，直到所有数据元素都排好序为止。在本节中，将介绍两种交换排序的方法：冒泡排序和快速排序。冒泡排序

冒泡排序(BubbleSort)的算法思想是：设排序表中有n个数据元素，首先对排序表中第一、二个数据元素的关键字Arr[0].Key和Arr[1].Key进行比较，如果Arr[0].Key>Arr[1].Key，则交换Arr[0]和Arr[1];然后对第二、三个数据元素做同样处理；重复此过程直到处理完最后两个相邻的数据元素。冒泡排序示例：冒泡排序的算法:template<classType>voidBubbleSort(sortlist<Type>&table){

inti=1;intfinish=0;

while(i<table.CurrentSize&&!finish){finish=1;//交换标志置为1,假定未交换

for(intj=0;j<.CurrentSize-i;j++)

if(table.Arr[j].GetKey()>table.Arr[j+1].GetKay()){Swap(table.Arr[j],table.Arr[j+1]);finish=0;}//交换标志置为0,表示有交换

i++;}}

在最坏情形下总的关键字比较次数和数据元素移动次数分别为：

因此在最坏情况下，冒泡排序的时间复杂度为O(n2）。冒泡排序需要一个附加存储空间以实现数据元素的交换。显然，冒泡排序算法是一种稳定的排序方法。快速排序

快速排序（QuickSort）又被称做分区交换排序，这是一种平均性能非常好的排序方法，其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关键字都小于或等于基准数据元素的关键字，右侧子表中所有数据元素的关键字都大于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。

快速排序过程示例：快速排序算法的描述如下：template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序区间lowhigh上，递归地进行快速排序

inti=low,j=high;element<Type>temp=table.Vector[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;

if(i<j){Table.Arr[i]=Table.Arr[j];i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;

if(i<j){Table.Arr[j]=Table.Arr[i];j--;}}Table.Arr[i]=temp//将基准元素就位

QuickSort(list,low,i-1);

//在左子区间递归进行快速排序

QuickSort(list,i+1,high);

//在右子区间递归进行快速排序}在n个元素的序列中，对一个数据元素定位所需时间为0(n)。若设T(n)是对n个元素的序列进行排序所需的时间，而且每次对一个数据元素正确定位后，正好把排序表划分为长度相等的两个子表，此时，总的计算时间为：T(n)≤cn+2T(n/2)其中，c是一个常数≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)…≤cnlog2n+nT(1)=O(nlog2n)

在一般情况下，设选为基准的数据元素是关键字第k小的，且等概率地取1、2、…、n，则有：

就是快速排序的平均计算时间，可以用归纳法证明，这个时间数量级也为0(nlog2n)。由于快速排序是递归的，就需要有一个栈存放每层递归调用时的指针和参数，其最大递归调用层次数与递归树的深度一致，理想情况为log2(n+1)，因此，要求的存储开销为0(log2n)。快速排序是一种不稳定的排序方法。插入排序

插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个的初始序列开始不断进行插入数据元素，直到最后一个数据元素插入到有序序列后，整个排序工作就完成了。直接插入排序

直接插入排序（InsertSort）的算法基本思想是：开始时把第一个数据元素作为初始的有序序列，然后依次从第二个数据元素开始把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1<i≤n)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入，原来位置及其以后的数据元素都向后顺移一个位置。如此进行n-1次插入就完成了排序。

顺序表上的直接插入排序

在顺序表上进行直接插入排序过程：直接插入排序算法的C++描述：template<classType>voidInsertionSort(sortlist<Type>&table){element<Type>temp;

intj;

for(inti=1;i<table.CurrentSize;i++){temp=table.Arr[i];j=i;

while(j>0&&temp.getKey()<table.Arr[j-1].getKey()){table.Arr[j]=table.Arr[j-1];j--;}table.Arr[j]=temp;}}

在最好情况下，即在排序前数据元素已经按关键字大小从小到大排好序了，每趟只需与前面的有序数据元素序列的最后一个数据元素的关键字比较1次，移动2次数据元素。所以，总的关键字比较次数为n-1，数据移动次数为2(n-1)，因此最好情况下的时间复杂度为O(n）；在最坏情况下，即第i趟插入时，第i+1个数据元素必须与前面i个数据元素都做关键字的比较，并且每做1次比较就要做1次数据元素移动，则总的关键字比较次数和数据移动次数分别为：

因此最坏情况下的时间复杂度为O(n2）。若排序表中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均，可得在平均情况下的关键字比较次数和数据元素移动次数约为n2／4，因此，直接插入排序的平均时间复杂度为O(n2)。根据上述分析可以得知：初始数据表越接近有序，直接插入排序的效率越高。这个结论是后面讨论希尔排序的基础。显然，在顺序表上的直接插入排序是一种稳定的排序方法。链表上的直接插入排序

右图给出了在链表上实现直接插入排序的示例，例子中用静态链表存储排序表，并把Arr[0]作为链表的表头结点。初始时，排序表中的数据元素结点形成一个单链表。在排序开始时，先把表头结点Arr[0]的next设为-1，表示有序链表为空表，p指向排序表的第一个数据元素结点。在静态链表上实现直接插入排序的算法：template<classType>intLinkInsertSort(sortlinklist<Type>&table){

intp,q,pre,r;p=table.Arr[0].getLink();//p指向第一个数据元素结点

table.Arr[0].setlink(-1);//形成初始链表

while(p!=-1){//当待排序序列中还存在数据元素结点时

q=table.Arr[0].getlink();pre=0;//前驱指针while(q!=-1){//找插入位置

if(table.Arr[q].getKey()<=table.Arr[p].getKey())pre=q;q=table.Arr[q].getLink();

else

break;}r=table.Arr[p].getLink();table.Arr[p].setlink(q);table.Arr[pre].setlink(p);//在pre与q之间插入p（即Arr[i]）

p=r;//准备插入下一个数据元素结点

}}

使用链表插入排序，无需移动数据元素的位置，代之以指针的修改共2n次。在插入第i个数据元素结点时，关键字比较次数最多为i次，关键字比较次数最少为1。因此，总的关键字比较次数最少为n-1，最多为：为了实现链表插入，在每个数据元素结点中增加了一个链域next，并使用了Arr[0]作为链表的表头结点。所以，总共用了n个附加指针域和一个附加数据元素结点。链表插入排序方法是稳定的。折半插入排序

折半插入排序算法与顺序表上进行直接插入排序的算法类似，只是在插入Arr[i]时，利用折半查找方法寻找Arr[i]的插入位置。折半插入排序的算法可描述为：template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp；

intleft,right;

for(inti=1;i<table.CurrentSize;i++){left=0;right=i-1;temp=table.Arr[i];

while(left<=right){

intmid=(left+right)/2;

if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}

for(intk=i-1;k>=left;k--)table.Arr[k+1]=table.Arr[k];table.Arr[left]=temp;}}

就平均性能而言，因为折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。折半插入排序的算法只能在顺序表存储结构下实现。

折半插入排序是一个稳定的排序方法。希尔排序

希尔排序(ShellSort)又称为缩小增量排序，它的算法基本思想是：设排序表中有n个数据元素，首先取一个整数d＜n作为间隔，将全部数据元素分为d个子表，所有相距为d的数据元素放在同一个子表中，在每一个子表中分别进行直接插入排序，然后缩小间隔d（例如取d=d/2），重复上述的子表划分和排序工作。如此循环，直到最后d＝1，将所有数据元素放在同一个序列中进行直接插入排序。

右图给出了有6个数据元素的排序表进行希尔排序的过程。第1趟取间隔d＝3，第2趟将间隔缩小为d＝d/2＝2，第3趟把间隔缩小为d＝d/2＝1，对整个序列进行直接插入排序，因为此时整个排序表已经达到基本有序，所以排序的效率比较高。希尔排序算法的C++描述：template<classType>voidShellsort(sortlist<Type>&table){element<Type>temp

intd=table.CurrentSize/2;//d是子表间隔

while(d){//循环直到d为零

for(inti=d;i<table.CurrentSize;i++){temp=table.Arr[i];

for(j=i;j>=d;j-=d)

if(temp.GetKey()<table.Arr[j-d].GetKey())table.Arr[j]=table.Arr[j-d]

else

break;table.Arr[j]=temp;}d=(int)(d/2);//修改子表间隔}}

利用大量的实验统计资料得出，当n很大时，关键字平均比较次数相数据元素平均移动次数大约在n1.25到1.6n1.25范围内，这是在利用直接插入排序作为子表排序方法的情况下得到的。在希尔排序中，由于数据元素的跳跃式移动，使得希尔排序不是稳定的排序方法。选择排序

选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下n-1个数据元素中再选取关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟(例如第i趟，i＝1，…，n-1)总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下1个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。直接选择排序

1.顺序表上的直接选择排序在顺序表存储结构下（设n个数据元素存储在向量Arr[0]Arr[n-1]中），直接选择排序的算法基本思想是：(1)开始时设i的初始值为0。(2)如果i<n-1，在数据元素序列Arr[i]Arr[n-1]中，选出具有最小关键字的数据元素Arr[k]；否则算法结束。(3)若Arr[k]不是这组数据元素中的第一个数据元素（i≠K），则将Arr[k]与Arr[i]这两数据元素的位置对调；(4)令i=i+1转步骤（2）。在顺序表上实现直接选择排序的示例

5在顺序表上直接选择排序算法的C++描述如下：template<classType>voidSelectSort(sortlist<Type>&table){

intk;

for(inti=0;i<table.CurrentSize-1;i++){k=i;

for(intj=i+1;j<table.CurrentSize;j++)

if(table.Arr[j].getKey()<table.Arr[k].getKey())k=j;

if(k!=i)Swap(table.Arr[i],table.Arr[k]);}}在直接选择排序中，关键字比较次数与数据元素的初始排列无关，总的关键字比较次数为:比较次数=(n-1)+(n-2)+…+1=n(n-1)/2数据元素的移动次数与排序表中数据元素的初始排列有关。当这组数据元素的初始状态是按其关键字从小到大有序的时候，数据元素的移动次数为0，达到最小值；而最坏情况是每一趟选择后都要进行交换，一趟交换需要移动数据元素3次。所以总的数据元素移动次数为3(n-1)。可见直接选择排序总的时间复杂度为O(n2）。由于在直接选择排序过程中，交换数据元素一般不是在相邻位置的数据元素之间进行，因此它不是一种稳定的排序方法。2．链表上的直接选择排序

在链表存储结构下直接选择排序的算法基本思想是：(1)开始时设h指向排序表的第一个数据元素结点；Arr[0].next设为-1，表示有序链表为空表；(2)设置搜索指针p指向h，如果p!=-1，表示排序表中还有数据元素没有被选出，继续步骤（3）；否则排序表中所有数据元素已经都有被选出，并插入到有序链表中，所以算法结束；(3)在排序表中选出具有最大关键字的数据元素结点，由q指向，pq指向q的前驱结点（如果存在）。(4)将q所指接点]插入到有序链表的第一个数据元素结点之前；(5)令p=h转步骤（2），准备下一次选择。在静态链表上实现直接选择排序的示例

在链表上进行直接选择排序算法的C++描述如下：template<classType>voidLinkSelectSort(sorlinktlist<Type>&table){

intp,q,pp,pq,h;h=p=table.Arr[0].getLink();table.Arr[0].setlink(-1);//形成初始有序链表

while(p!=-1){q=pq=pp=p;设置初始搜索指针

p=table.Arr[p].getLink();while(p!=-1){

if(table.Arr[p].getKey()>=table.Arr[q].getKey()){q=p;pq=pp;}pp=p;p=table.Arr[p].getLink();}

if(h=q){h=table.Arr[q].getLink();table.Arr[q].setLink(table.Arr[0].getLink());table.Arr[0].setLink(q);}

else

{table.Arr[pq].setLink(table.Arr[q].getLink());table.Arr[q].setLink(table.Arr[0].getLink());table.Arr[0].setLink(q);}p=h;//准备下一次选择

}}与在顺序表上的直接选择排序一样。在链表上进行直接选择排序，关键字比较次数与数据元素的初始排列无关，总的关键字比较次数为:比较次数=(n-1)+(n-2)+…+1=n(n-1)/2

在链表上进行直接选择排序不需要进行数据元素的移动，每一趟选出数据元素后只需将其插入到有序表的第一个数据元素之前。可见在链表上进行直接选择排序总的时间复杂度也为O(n2）。链表上的直接选择排序也是一种稳定的排序方法。锦标赛排序

锦标赛排序的算法思想与体育比赛类似。首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来，然后对这n／2个数据元素再两两分组，分别按关键字进行比较，…，如此重复，直到选出一个关键字最小的数据元素为止。

锦标赛排序示例：

锦标赛排序构成的树是完全二叉树，其高度为Log2n+1，其中n为排序表中数据元素个数。因此，除第一次选出具有最小关键字的数据元素需要进行n-1次关键字比较外，重构优胜者树，选出具有次小、再次小、…关键字的数据元素所需的关键字比较次数均为0(Log2n)。所以，总的关键字比较次数为0(nLog2n)。数据元素的移动次数与关键字的比较次数相当，所以锦标赛排序总的时间复杂度为0(nlog2n)。锦标赛排序也是一种不稳定的排序方法。堆排序

堆排序的算法基本思想是：（1）对排序表中的数据元素，利用堆的调整算法形成初始堆。（2）输出堆顶元素。（3）对剩余元素重新调整形成堆。（4）重复执行第（2)、(3)步，直到所有数据元素被输出。堆排序的示例

建立最大堆的调整算法：template<classType>voidMinHeap<Type>::FilterDown(const

intstart,

const

intEndOfHeap){//向下调整使从start开始到EndOfHeap为止的子表成为最大堆

inti=start,j=2*i+1;//j为i的左孩子

Typetemp=heapArr[i];

while(j<=EndOfHeap){

if(j<EndOfHeap&&table.Arr[j].getkey()<table.Arr[j+1].getkey())j++;//在两个孩子中选关键字较小者

if(temp.getkey()>=table.Arr[j].getkey())

break;

else{table.Arr[i]=table.Arr[j];i=j;j=2*j+1;}}table.Arr[i]=temp;}堆排序算法的C++描述如下：template<classType>void

HeapSort(sortlist<Type>&table){

for(inti=(table.CurrentSize-2)/2;i>=0;i--)FilterDown(i,table.CurrentSize-1);//初始建堆

for(i=table.CurrentSize-1;i>=1;i--){Swap(table.Arr[0],table.Arr[i]);FilterDown(0,i-1);//重建最大堆

}}

堆排序算法的时间复杂性可用关键字的比较次数来测度。若设堆中有n个结点，且2k-1n2k，则对应的完全二叉树有k层。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法FilterDown()，一个数据元素每下调一层需要进行2次关键字的比较，最多下调到最底层，因此该循环所用的计算时间为：其中，i是层序号，2i-1是第i层的最大结点数，(k-i-1)是第i层结点下调到最底层（第k层）所需的调整次数。

在第二个for循环中，调用了n-1次FilterDown()算法，每次调用总是将位于根上的数据元素最多下调到当前堆的最底层。所以该循环的计算时间为O(nlog2n)。因此，堆排序的时间复杂性为O(nlog2n)。该算法的空间复杂性为O(1)。堆排序是一种不稳定的排序方法。归并排序

所谓归并，就是将两个或两个以上的有序表合并成一个新的有序表。如下图所示，有两个已经排好序的有序表A[1]A[n]和B[1]B[m]（在图中只给出了它们的关键字），通过归并把它们合成一个有序表C[1]C[m+n]。两路归并算法的C++描述：template<classType>voidmerge(sortlist<Type>&sourceTable,sortlist<Type>&mergedTable,

const

intleft,const

intmid,const

intright){

inti=left,j=mid+1,k=left;//指针初始化

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

if(sourceTable.Arr[i].getKey()<=sourceTable.Arr[j].getKey()){mergedTable.Arr[k]=sourceTable.Arr[i];i++;k++;}

else{mergedTable.Arr[k]=sourceTable.Arr[j];j++;k++;}

if(i<=mid)

for(intp=k,q=i;q<=mid;p++,q++)mergedTable.Arr[p]=sourceTable.Arr[q];

else

for(intp=k,q=j;q<=right;p++,q++)mergedTable.Arr[q]=sourceTable.Arr[p];}两路归并排序

两路归并排序就是利用两路归并算法进行排序。其算法基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表(以后称它们为归并项)，先做两两归并，得n/2个长度为2的归并项(如果n为奇数，则最后一个归并项的长度为1)；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。两路归并排序的示例：一趟归并的算法描述如下：template<classType>voidMergePass(sortlist<Type>&sourceTable,sortlist<Type>&mergedTable,const

intlen){

inti=0;

while(i+2*len<=CurrentSize-1){merge(sourceTable,mergedTable,i,i+len-1,i+2*len-1);i+=2*len;}

if(i+len<=CurrentSize-1)merge(sourceTable,mergedTable,i,i+len-1,CurrentSize-1);

else

for(intj=i;j<=CurrentSize-1;j++)mergedTable.Arr[j]=sorceTable.Arr[j];}两路归并排序算法描述如下：template<classType>voidMergeSort(sortlist<Type>&table){sortlist<Type>&tempTable;

intlen=1;

while(len<table.CurrentSize){MergePass(table,tempTable,len);len*=2;MergePass(tempTable,list,len);len*=2;}delete[]tempTable;}

在两路归并排序算法中，函数MergePass()做一趟归并，要调用merge()函数n/(2*len)

O(n/len)次，而每次merge()要执行比较次数不超过2*len-1，为O(len)，函数MergeSort()调用MergePass()正好log2n

次，所以两路归并排序算法总的时间复杂度为O(nlog2n)。两路归并排序占用附加存储较多，需要另外一个与原待排序数据元素数组同样大小的辅助数组，所以其空间复杂度为O(n）。两路归并排序是一个稳定的排序方法。递归的归并排序

在递归的归并排序方法中，首先要把整个排序表划分为长度大致相等的左右两个部分，分别称之为左子表和右子表，对这两个子表分别进行归并排序（递归），然后再把已排好序的这两个子表进行两路归并，得到一个有序表。

递归的归并排序示例：

在递归的归并排序过程中，如果使用前面给出的两路归并算法，需要进行数组元素的传递，这非常影响归并的效率。如果排序表采用链表的存储表示，可以得到一种有效的归并排序算法。在此排序表以静态链表存储，设待排序的数据元素存放在类型为的静态链表table中。table.Arr[0]用于表示结果链表的头结点。函数linkListMerge()是将两个有序的单链表归并成一个有序单链表的算法。静态链表上的递归归并排序示例：在静态链表上实现两路归并的算法描述如下：template<classType>intlinkListMerge(sortlinklist<Type>&table,

const

intp,const

intq){

intk=0,i=p,j=q;//初始化指针,其中k为结果链表的尾结点指针,i、j为搜索指针

while(i!=-1&&j!=-1)

if(table.Arr[i].getKey()<=table.Arr[j].getKey()){table.Arr[k].setLink(i);k=i;i=table.Arr[i].getLink();}

else{table.Arr[k].setLink(j);k=j;j=table.Arr[j].getLink();}

if(j!=-1)table.Arr[k].setlink(j);

elsetable.Arr[k].setLink(i);

returntable.Arr[0].getLink();}递归归并排序算法：template<classType>intlinkListMergeSort(sortlinklist<Type>&table,

const

intlow,const

inthigh){

if(low>=high)returnlow;

intmid=(low+high)/2;

returnlinkListMerge(table,linkListMergeSort(table,low,mid),linkListMergeSort(table,mid+1,right));}

在静态链表上实现的递归归并排序算法，通过链接指针的修改以实现数据元素接点的逻辑有序链接，因此不需要数据元素移动。计算时间可以用数据元素关键字的比较次数来测量。算法的递归深度为O(log2n)，所以总的时间复杂度为0(nlog2n)。它也是一种稳定的排序方法。

基数排序

基数排序又被称为桶排序。与前面介绍的几种排序方法相比较，基数排序和它们有明显的不同。前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上，所以可以称为基于比较的排序；而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起。通过使用对多关键字进行排序的这种“分配”和“收集”的方法，基数排序实现了对多关键字进行排序。多关键字排序

每张扑克牌有两个“关键字”：花色和面值。其大小顺序为：花色：＜＜＜面值：2＜3＜……＜K＜A扑克牌的大小先根据花色比较，花色大的牌比花色小的牌大；花色一样的牌再根据面值比较大小。所以，将扑克牌按从小到大的次序排列，可得到以下序列：

2，…，A，2，…，A，2，…，A，2，…，A

这种排序相当于有两个关键字的排序，一般有两种方法实现。其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值从小到大的次序排序，最后把已排好序的四堆牌按花色从小到大次序叠放在一起就得到排序的结果。其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后将这十三堆牌按面值从小到大的顺序叠放在一起，再把整副牌按顺序根据花色再分成四堆（每一堆牌已按面值从小到大的顺序有序），最后将这四堆牌按花色从小到大合在一起就得到排序的结果。

假定排序表中有n个数据元素（Arr[0]、Arr[1]、…、Arr[n-1]）。其中，每个数据元素Arr[i]（0≤i≤n-1）含有d个关键字(ki1，ki2，…，kid)。如果对于序列中任意两个数据元素Arr[j]和Arr[i](0≤j<i≤n-1)都满足：

(kj1，kj2，…，kjd)<(ki1，ki2，…，kid)

则称数据元素序列以关键字(k1，k2，…，kd)有序。在次，k1称为最高位关键字，kd称为最低位关键字。

实现多关键字排序有两种常用的方法，一种方法被称为最高位优先法MSD(MostSignificantDigitfirst)，另一种方法被称为最低位优先法LSD(LastSignificantDigitfirst)。最高位优先法通常是一个递归的过程：首先根据最高位关键字k1进行排序，按k1值的不同，将整个排序表分成若干个子表，每个子表中的数据元素具有相同的关键字k1。然后分别对每一个每个子表中的数据元素根据关键字（k2，…，kd）用最高位优先法进行排序。如此递归，直到对关键字kd完成排序为止。

最低位优先法是首先依据最低位关键字kd对排序表中所有数据元素进行一趟排序，然后依据次低位关键字kd-1对上一趟排序的结果再排序，依次重复，直到按关键字k1最后一趟排序完成，就可以得到排序的结果。使用这种排序方法时，每一趟排序都是对整个排序表操作，且需采用稳定的排序方法。链式基数排序

基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”这两种运算对单关键字进行排序。在这种方法中，把关键字k看成是一个d元组：

(k1，k2，…，kd)

其中的每一个分量也可以看成是一个关键字，假设分量kj(1≤j≤d)有radix种取值，则称radix为基数。基数排序的算法思想：对d元组中的每一个分量kj，把排序表中的所有数据元素，按kj的取值，先“分配”到radix个队列（桶）中去，然后再按各队列的顺序，依次把数据元素从队列中“收集”起来，这样所有数据元素按kj取值排序完成。如果对排序表中所有数据元素按关键字（k1，k2，…，kd），依次对各分量kj（j＝d，d-1