8.4 其他排序方法简介
8.4 其他排序方法简介
8.4.1 归并排序
|
图8-22 以文件甲和乙为例的归并排序示意图 |
由于归并是在相邻的两个有序表中进行，因此，上述排序方法也叫二路归并排序。如果归并操作在相邻的多个有序表中进行，则叫多路归并排序。在此只讨论二路归并排序（简称归并排序）。
上述归并排序的前提是将两个已经排序好的数据合并在一个文件中。假使有一堆未排序的数据，可以将其分割成两部分，一直分割到每一部分只有一个数据时，再将它们两两归并。假设有下列8个键值18，2，20，34，12，32，6，16，如图8-23所示。
图8-23 将无序数据进行归并排序的示意图
从图8-23中，大致可以发现最后归并的操作是对两个排序好的数据加以归并的过程。
对于归并排序算法，当有n个元素时，需要élog2nù趟归并，每一趟归并，其关键字比较次数不超过n-1次，元素移动次数都是n，因此，归并排序的时间复杂度为O(nlog2n)。
假设R[i]和R[j]是两个相邻有序表中关键字相同的元素，而且i<j，归并算法归并两个有序表时，发现条件R[i].key<=R[j].key满足，就将R[i]写入R1中，这样就保证了R[i]和R[j]的相对位置不改变。所以归并排序算法是稳定的。
归并算法的程序实例如下：
/*归并排序*/
#include <stdio.h>
void select_sort(int[],int);
void merge_sort(int[],int[],int[],int,int);
void main()
{
int data1[10],data2[10],data3[20];
int size1=0,size2=0,i;
/*要求输入两组数据作归并*/
printf("\nPlease enter data 1 to sort ( enter 0 when end ):\n");
printf("Number : ");
do
{
scanf("%d", &data1[size1]);
} while(data1[size1++]!=0);
printf("Please enter data 2 to sort ( enter 0 when end ):\n");
printf("Number : ");
do
{
scanf("%d",&data2[size2]);
}
while(data2[size2++]!=0);
/*先使用选择排序将两组数据排序，再作归并*/
select_sort(data1,--size1);
select_sort(data2,--size2);
for(i = 0; i < 60; i++) printf("-");
printf("\nData 1 : ");
for(i=0;i<size1;i++)
printf("%d ",data1[i]);
printf("\n");
printf("Data 2 : ");
for(i=0;i<size2;i++)
printf("%d ",data2[i]);
printf("\n");
for(i=0;i<60;i++) printf("-");
printf("\n");
merge_sort(data1, data2, data3, size1, size2);
for(i=0;i<60;i++) printf("-");
printf("\nSorting: ");
for(i=0;i<size1+size2;i++)
printf("%d ",data3[i]);
}
void select_sort(int data[], int size)
{
int base,compare,min,temp;
for(base=0;base<size-1;base++)
{
min = base;
for(compare=base+1;compare<size;compare++)
if(data[compare]<data[min])
min=compare;
temp=data[min];
data[min]=data[base];
data[base]=temp;
}
}
void merge_sort(int data1[],int data2[],int data3[],int size1,int size2)
{
int arg1,arg2,arg3, i;
data1[size1]=32767;
data2[size2]=32767;
arg1=0;
arg2=0;
for(arg3=0;arg3<size1+size2;arg3++)
{
/*比较两组数据，数据小的先存于归并后的数列*/
if(data1[arg1]<data2[arg2])
{
data3[arg3]=data1[arg1];
arg1++;
}
else
{
data3[arg3]=data2[arg2];
arg2++;
}
printf("Access : ");
for(i=0;i<arg3+1;i++)
printf("%d ",data3[i]);
printf("\n");
}
}
以上程序输出结果为：
Please enter data 1 to sort ( enter 0 when end ):
Number : 2 10 12 18 25 0
Please enter data 2 to sort ( enter 0 when end ):
Number : 6 16 20 32 34 0
------------------------------------------------------------
Data 1 : 2 10 12 18 25
Data 2 : 6 16 20 32 34
------------------------------------------------------------
Access : 2
Access : 2 6
Access : 2 6 10
Access : 2 6 10 12
Access : 2 6 10 12 16
Access : 2 6 10 12 16 18
Access : 2 6 10 12 16 18 20
Access : 2 6 10 12 16 18 20 25
Access : 2 6 10 12 16 18 20 25 32
Access : 2 6 10 12 16 18 20 25 32 34
------------------------------------------------------------
Sorting: 2 6 10 12 16 18 20 25 32 34
8.4.2 基数排序
与前面介绍的几种排序方法不同，基数排序不比较关键字的大小。它是根据关键字中各位的值，通过对待排序的n个元素进行若干趟“分配”与“收集”来实现排序的。
设待排序的线性表中每个元素的关键字都是d位的十进制正整数。在排序过程中需要对该线性表进行d趟的分配与收集处理，每趟处理方法是相同的。在进行第j（j=1，2，…，d）趟处理时，首先按元素在线性表中的排列顺序，依次将每个元素插入到编号为0～9的某个队列（关键字右起第j位上的值是几就插入几号队列），这个过程叫做分配；然后，按队列编号从小到大、同一队列按插入先后的顺序，从队列中取出所有元素，重新构成一个线性表，这个过程叫做收集。在进行了d趟的分配与收集之后，排序过程结束。
【例8-3】 已知有10个待排序的记录，它们的关键字序列为{75,87,68,92,88,61,77,96,80,
72}，给出用基数排序法进行排序的过程。
解：基数排序过程如图8-24所示。
图8-24 基数排序过程
如下基数排序算法实现以r为基数，采用从低位到高位的排序方法，其中，参数p为存储的待排序序列的链表指针，r为基数，d为关键字位数。
#define MAXE 20 /*线性表中最多元素个数*/
#define MAXR 10 /*基数的最大取值*/
#define MAXD 8 /*关键字位数的最大取值*/
typedef struct node
{
char data[MAXD]; /*记录的关键字定义的字符串*/
struct node *next;
} RecType;
void RadixSort(RecType *&p,int r,int d)
/*p为待排序序列链表指针，r为基数，d为关键字位数*/
{
RecType *head[MAXR],*tail[MAXR],*t;/*定义各链队的首尾指针*/
int i,j,k;
for (i=d-1;i>=0;i--) /*从低位到高位做d趟排序，因为75存放在串中为"57"*/
{
for (j=0;j<r;j++) /*初始化各链队首、尾指针*/
head[j]=tail[j]=NULL;
while (p!=NULL) /*对于原链表中每个节点循环*/
{
k=p->data[i]-'0'; /*找第k个链队*/
if(head[k]==NULL) /*进行分配，即采用尾插法建立单链表*/
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p=p->next; /*取下一个待排序的元素*/
}
p=NULL;
for(j=0;j<r;j++) /*对于每一个链队循环*/
if(head[j]!=NULL) /*进行收集*/
{
if(p==NULL)
{
p=head[j];
t=tail[j];
}
else
{
t->next=head[j];
t=tail[j];
}
}
t->next=NULL; /*最后一个节点的next域置NULL*/
}
}
为了实现上例的功能，设计如下主函数：
void main()
{
RecType *h=NULL,*p,*t;
char *A[]={"75","87","68","92","88","61","77","96","80","72"};
int i,n=10;
for(i=0;i<n;i++) /*构造不带头节点的单链表h*/
{
p=(RecType *)malloc(sizeof(RecType));
strcpy(p->data,A[i]);
if(h==NULL)
{
h=p;
t=h;
}
else
{
t->next=p;
t=p;
}
}
t->next=NULL;
printf("排序前:");
for(i=0;i<n;i++)
printf("%3s",A[i]);
printf("\n");
RadixSort(h,10,2); /*递归调用基数排序算法*/
printf("排序后:");
p=h;
while(p!=NULL)
{
printf("%3s",p->data);
p=p->next;
}
printf("\n");
}
本程序的执行结果：
排序前:75 87 68 92 88 61 77 96 80 72
排序后:61 68 72 75 77 80 87 88 92 96
基数排序的执行时间不仅与线性表长度n有关，而且还与关键字的位数d、关键字的基数r（对于十进制数，r=10）有关。一趟分配所需时间为O(n)，一趟收集所需时间为O(r)，因总共进行了d趟分配与收集，所以总的执行时间为O(d(n+r))。
基数排序是稳定的，队列的先进先出特性保证了这一点。
8.4.3 二叉树排序
二叉树排序是先将所有的数据建立成二叉查找树，再利用中序法来遍历，步骤如下：
（1）将第一个数据放在根节点。
（2）进来的数据都与根节点比较，若比根节点大，则置于右子树；反之则置于左子树。
（3）二叉查找树建立完后，利用中序法遍历，即可得到由小至大的排序数据。
假设有10个数据分别是18，2，20，34，12，32，6，16，25，10。建立二叉树过程如图8-25和图8-26所示。
图8-25 插入18，2，20，34后的二叉树示意图
图8-26 插入12，32，6，16，25，10后的二叉树示意图
最后利用中序法来遍历就可完成排序（由小至大）。
二叉树排序的一个完整程序实例如下：
/*二叉树排序*/
#include <stdio.h>
#include <stdlib.h>
struct data
{
int num;
struct data *lbaby,*rbaby;
} *root,*tree,*leaf;
void find(int,struct data *);
void output(struct data *);
void main()
{
int data[10]={75,23,98,44,57,12,29,64,38,82};
int i;
printf("\n<< Binary tree sort >>\n");
printf("\nNumber : ");
for(i=0;i<10;i++)
printf("%d ",data[i]);
puts("");
for(i=0;i<60;i++) printf("-");
root=(struct data *) malloc(sizeof(struct data));
/*建树根*/
root->num=data[0];
root->lbaby=NULL;
root->rbaby=NULL;
printf("\nAccess : ");
output(root);
leaf=(struct data *) malloc(sizeof(struct data));
for(i=1;i<10;i++)
{
leaf->num=data[i];
leaf->lbaby=NULL;
leaf->rbaby=NULL;
find(leaf->num,root);
if(leaf->num>tree->num) /*若比父节点大，则放在右子树*/
tree->rbaby=leaf;
else /*否则放在左子树*/
tree->lbaby=leaf;
printf("\nAccess : ");
output(root);
leaf=(struct data *) malloc(sizeof(struct data));
}
puts("");
for(i=0;i<60;i++) printf("-");
printf("\nSorting: ");
output(root);
}
/*寻找新节点存放的位置*/
void find(int input,struct data *papa)
{
if((input>papa->num) && (papa->rbaby !=NULL))
find(input,papa->rbaby);
else if((input<papa->num) && (papa->lbaby !=NULL))
find(input,papa->lbaby);
else
tree=papa;
}
/*输出数据*/
void output(struct data *node) /*用中序遍历将数据输出*/
{
if(node !=NULL)
{
output(node->lbaby);
printf("%d ",node->num);
output(node->rbaby);
}
}
上述程序的输出结果是：
<< Binary tree sort >>
Number : 75 23 98 44 57 12 29 64 38 82
------------------------------------------------------------
Access : 75
Access : 23 75
Access : 23 75 98
Access : 23 44 75 98
Access : 23 44 57 75 98
Access : 12 23 44 57 75 98
Access : 12 23 29 44 57 75 98
Access : 12 23 29 44 57 64 75 98
Access : 12 23 29 38 44 57 64 75 98
Access : 12 23 29 38 44 57 64 75 82 98
------------------------------------------------------------
Sorting: 12 23 29 38 44 57 64 75 82 98