延安大学计算机学院试验报告纸附页

 

第二篇：数据结构中的排序算法总结

=============================================================

文章中谈及的排序算法包括：冒泡排序；选择排序；插入排序；快速排序；希尔排序；堆排序；归并排序；基数排序。

注：头文件“array.h”内容是线性表的建立与线性表中元素的输出。线性表中的元素的输入是从1空间开始的，0空间作为中间变量或者作为暂存单元。每一个排序算法的程序都包含头文件“array.h”，运行前需要先生成“array.h”头文件，运行时头文件与排序的源文件必须在同一个文件夹下。建议不要在同一个工作空间同进运行多个排序算法的源文件，否则编译器会报错。

头文件array.h的代码---------------------------------------------------------------------------- #define N 100

typedef int datatype;

typedef struct{//定义线性表结构

datatype elem[N];

int length;

}SeqList;

void create_array(SeqList *list)//创建线性表

{

list->length=0;//初始化

datatype x;

printf("*-----输入一组随机数(以结束!)-----*\n\n");

scanf("%d",&x);

while(x)//输入线性表元素

{

list->length++;

list->elem[list->length]=x;

scanf("%d",&x);

}

}

void out(SeqList *s)//输出线性表元素

{

int i;

printf("\n*-----输入的随机数排序结果如下-----*\n\n");

for(i=1;i<=s->length;i++)

printf("%5d",s->elem[i]);

printf("\n\n");

} 向记录的指针或移动记录本身。

冒泡排序算法-------------------------------------------------------------------------------------

(1)从下往上：第1趟扫描从记录的R[1..n]的底部向上依次比较相邻的两个气泡的重量，若发现轻者在下，重者在上，则交换二者的位置。第1趟完毕后，“最轻”的气泡就飘浮到该区间的顶部。第2趟扫描的记录为R[2..n]，扫描完毕后“次

轻”的气泡飘浮到R[2]的位置上。以此类推，直至R[1..i]变为新的有序区。 #include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//从上往下的冒泡排序算法

void sort(SeqList *list)

{

int i,j;

for(i=1;i<list->length;i++)

for(j=1;j<=list->length-i;j++)

//从小到大排序

if(list->elem[j]>list->elem[j+1])

{//0空间作为中间变量进行前后交换

list->elem[0]=list->elem[j];//

list->elem[j]=list->elem[j+1];

list->elem[j+1]=list->elem[0];

}

}

/*--------------------------------------------------*/

void main()//检测算法的正确性

{

SeqList range;

create_array(&range);

sort(&range);

out(&range);

}

-------------------------------------------------------------------------------------------------------

(2)从上往下：第1趟扫描从记录的R[1..n]的顶部向下依次比较相邻的两个气泡的重量，若发现重者在上，轻者在下，则交换二者的位置。第1趟完毕后，“最重”的气泡就沉到该区间的底部。第2趟扫描的记录为R[1..n-1]，扫描完毕后“次重”的气泡飘浮到R[n-1]的位置上。以此类推，直至R[i..n]变为新的有序区。 #include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//从下往上的冒泡排序算法

void sort(SeqList *digit)

{

int i,j;

for(i=1;i<digit->length-1;i++)

for(j=digit->length;j>i;j--)

//从小到大排序

if(digit->elem[j]<digit->elem[j-1])

{//0空间作为中间变量进行前后交换

digit->elem[0]=digit->elem[j];

digit->elem[j]=digit->elem[j-1];

digit->elem[j-1]=digit->elem[0];

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

sort(&range);

out(&range);

}

选择排序算法------------------------------------------------------------------------------------- 第i趟排序开始进行，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)，该趟排序则是从当前无序区中选择出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为新的有序区和新的无序区。 #include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//选择排序算法

void sort(SeqList *digit)

{

int i,j,k;

for(i=1;i<digit->length;i++)

{

k=i;//记录下标

for(j=i+1;j<=digit->length;j++)

if(digit->elem[k]>digit->elem[j])

k=j;//记录较小值的下标

if(k!=i)//非本身则交换

{//0空间作为中间变量进行交换

digit->elem[0]=digit->elem[k];

digit->elem[k]=digit->elem[i];

digit->elem[i]=digit->elem[0];

}

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

sort(&range);

out(&range);

}

插入排序算法------------------------------------------------------------------------------------- 每次将一个待排序的记录，按其关键字大小插入到前面已经排好的子文件中的适当位置，直到全部记录插入完成为止。

#include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//插入排序算法

void sort(SeqList *r)

{

int i,j;

for(i=2;i<=r->length;i++)

if(r->elem[i]<r->elem[i-1])

{

r->elem[0]=r->elem[i];//置为空间

for(j=i-1;r->elem[0]<r->elem[j];j--)

r->elem[j+1]=r->elem[j];//从后往前移位

r->elem[j+1]=r->elem[0];//置为适当位置

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

sort(&range);

out(&range);

}

快速排序算法------------------------------------------------------------------------------------- 在R[low..high]中任选择一个记录作为基准，以引基准将当前无序区划分为左或右两个较小的区间R[low..pivotpos-1]和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录，右边的子区间中所有记录的关键字均大于等于基准记录。通过递归调用快速排序对左、右两个子区间R[low..pivotpos-1和R[pivotpos+1..high]排序。

#include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//快速排序算法

int sort(SeqList *t,int low,int high)

{

t->elem[0]=t->elem[low];//置为空间

while(low<high)

{ while(low<high&&t->elem[high]>=t->elem[0])

high--;//比空间值大则往前

t->elem[low]=t->elem[high];//比空间值小时传给low

while(low<high&&t->elem[low]<=t->elem[0])

low++;//比空间值小则往后

t->elem[high]=t->elem[low];//比空间值大时传给high

}

t->elem[low]=t->elem[0];

return low;//返回空间值存放的位置

}

void qsort(SeqList *r,int low,int high)

{

int mid;

if(low<high)

{ mid=sort(r,low,high);

qsort(r,low,mid-1);//递归左子块

qsort(r,mid+1,high);//递归右子块

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

qsort(&range,1,range.length);

out(&range);

}

希尔排序算法------------------------------------------------------------------------------------- 先取定一个小于n的整数作为第一个增量，把文件中的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二相增量d2?d1重复上述的分组和排序，直至所取的增量dt?1(dt?dt?1...?d2?d1)，即所有的记录放在同一组中进行直接插入排序为止。 #include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//希尔排序算法

void sort(SeqList *R,int d)

{

int i,j;

for(i=d+1;i<=R->length;i++)

if(R->elem[i]<R->elem[i-d])

{

R->elem[0]=R->elem[i];//R[0]是暂存空间，非哨兵

j=i-d;

do//查找R[i]的插入位置

{

R->elem[j+d]=R->elem[j];//后移

j=j-d;//查找前一记录

}while(j>0&&R->elem[0]<R->elem[j]);

R->elem[j+d]=R->elem[0];

}

}

void ssort(SeqList *R)

{

int mark=R->length;//增量初值

do

{

mark=mark/3+1;//下一增量

sort(R,mark);

}while(mark>1);

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

ssort(&range);

out(&range);

}

堆排序算法---------------------------------------------------------------------------------------- 将初始文件R[1..n]建成一个大根堆；将无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为大根堆。如此反复，执行n-1趟排序得到有序区R[1..n]。

#include<stdio.h>

#include"array.h"

/*--------------------------------------------------*/

//堆排序算法

void sort(SeqList *R,int low,int high)

{//调整为大根堆

int large;//记录左右孩子的较大者

R->elem[0]=R->elem[low];//调整结点置为空间 for(large=2*low;large<=high;large*=2)

{

if(large<high&&R->elem[large]<R->elem[large+1]) large++;//记录当前左右孩子的较大者 if(R->elem[0]>=R->elem[large])

break;//不大于调整结点则结束

R->elem[low]=R->elem[large];

low=large;//记录新的调整结点

}

R->elem[low]=R->elem[0];

}

void built(SeqList *R)

{//构造大根堆

int i;

for(i=R->length/2;i>0;i--)

sort(R,i,R->length);//调整为堆

}

void hsort(SeqList *R)

{

int i;

built(R);//建立初始堆

for(i=R->length;i>1;i--)

{//交换堆顶和最后一个记录

R->elem[0]=R->elem[1];

R->elem[1]=R->elem[i];

R->elem[i]=R->elem[0];

sort(R,1,i-1);//重新调整为堆

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

hsort(&range);

out(&range);

}

归并排序算法-------------------------------------------------------------------------------------

(1)自底向上：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到?n/2?个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)，因此本趟归并完后，前?n/2?-1个有序文件长度为2，但最后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的?n/2?个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。

#include<stdio.h>

#include<malloc.h>

#include"array.h"

/*--------------------------------------------------*/

//归并排序的迭代算法

void sort(SeqList *R,int low,int m,int high)

{

int i=low,j=m+1,p=0;//初始化

SeqList *T;//局部向量

if(high-low+1>0)

T=(SeqList *)malloc(sizeof(SeqList));

while(i<=m&&j<=high)//两子文件非空时取其小者输出到T上

T->elem[p++]=(R->elem[i]<=R->elem[j])?R->elem[i++]:R->elem[j++]; while(i<=m)//第个子文件非空则复制剩余记录到T中

T->elem[p++]=R->elem[i++];

while(j<=high)//第个子文件非空则复制剩余记录到T中

T->elem[p++]=R->elem[j++];

for(p=0,i=low;i<=high;p++,i++)

R->elem[i]=T->elem[p];//归并完成后再复制到R中

}

void pass(SeqList *R,int n)

{//进行一次归并排序

int i;

for(i=1;i+2*n-1<=R->length;i=i+2*n)

//归并长度为n的两个相邻的子文件

sort(R,i,i+n-1,i+2*n-1);

if(i+n-1<n)

sort(R,i,i+n-1,n);//归并最后两个子文件

}

void msort(SeqList *R)

{//进行二路归并排序

int i;

for(i=1;i<=R->length;i*=2)

pass(R,i);

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

msort(&range);

out(&range);

}

-------------------------------------------------------------------------------------------------------

(2)自顶向下：将当前区间一分为二，求分裂点mid??(low?high)/2?；递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个序的区间R[low..high]。

#include<stdio.h>

#include<malloc.h>

#include"array.h"

/*--------------------------------------------------*/

//归并排序的递归算法

void sort(SeqList *R,int low,int m,int high)

{

int i=low,j=m+1,p=0;//初始化

SeqList *T;//局部向量

if(high-low+1>0)

T=(SeqList *)malloc(sizeof(SeqList));

while(i<=m&&j<=high)//两子文件非空时取其小者输出到T上

T->elem[p++]=(R->elem[i]<=R->elem[j])?R->elem[i++]:R->elem[j++]; while(i<=m)//第个子文件非空则复制剩余记录到T中

T->elem[p++]=R->elem[i++];

while(j<=high)//第个子文件非空则复制剩余记录到T中

T->elem[p++]=R->elem[j++];

for(p=0,i=low;i<=high;p++,i++)

R->elem[i]=T->elem[p];//归并完成后再复制到R中

}

void msort(SeqList *R,int low,int high)

{//进行二路归并排序

int mid;

if(low<high)

{

mid=(low+high)/2;//分解为两部分

msort(R,low,mid);//递归左子块

msort(R,mid+1,high);//递归右子块

sort(R,low,mid,high);//组合为一个有序序列

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

msort(&range,1,range.length);

out(&range);

}

基数排序算法------------------------------------------------------------------------------------- 设置若干个箱子，从低位到高位的每位都依次对Kj(j?d?1,d?2,...,0)进行分配与收集：依次扫描排序的记录R[0],R[1],…,R[n-1]，把关键字等于k的记录全都装到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾接起来(收集)。 #include<stdio.h>

#include<malloc.h>

#define Radix 10

#define KeySize 5//整型变量最高位数

#include"array.h"

typedef struct node{//定义队列结点

datatype data;

struct node *next;

}QueueNode;

typedef struct{

QueueNode *front,*rear;

}LinkQueue;

//初始化链队列

void InitQueue(LinkQueue *s)

{

s->front=s->rear=NULL;

}

//判断链队列为空

int EmptyQueue(LinkQueue *s)

{

if(s->front==NULL)

return 1;

else return 0;

}

//入队列

void InQueue(LinkQueue *s,datatype x)

{

QueueNode *p;//初始化新的结点

p=(QueueNode *)malloc(sizeof(QueueNode)); p->data=x;

p->next=NULL;

if(EmptyQueue(s))//新结点插入空队列

s->front=s->rear=p;

else//链队列非空则插入队尾

{

s->rear->next=p;

s->rear=p;

}

}

//出队列

datatype OutQueue(LinkQueue *s)

{

datatype x;

QueueNode *p;

if(!EmptyQueue(s))

{//队非空时则出队列

p=s->front;

x=p->data;

s->front=p->next;

if(s->rear==p)//出队列结点为队头

s->rear=NULL;

free(p);//删除已出队列的结点

return x;

}

}

/*--------------------------------------------------*/

//基数排序算法

void sort(SeqList *p,LinkQueue R[],int j)

{

int i,k;

j=KeySize-j;//确定关键字从个位起的位数

for(i=1;i<=p->length;i++)

{//依次扫描R[i]，将其入队

p->elem[0]=p->elem[i];

for(k=1;k<j;k++)

p->elem[0]=p->elem[0]/10;

p->elem[0]=p->elem[0]%10;//取关键字的第j位数字 InQueue(&R[p->elem[0]],p->elem[i]);//将R[i]入队 }

}

void collect(SeqList *p,LinkQueue R[])

{//收集非空链队的记录

int i=1,j;

for(j=0;j<Radix;j++)

while(!EmptyQueue(&R[j]))

//出队记录输出到R[i]中

p->elem[i++]=OutQueue(&R[j]);

}

void rsort(SeqList *list)

{

LinkQueue R[Radix];//10个为链队列的基数

int i;

for(i=0;i<Radix;i++)//初始化

InitQueue(&R[i]);//队列置为空

for(i=KeySize-1;i>=0;i--)

{

sort(list,R,i);//分配

collect(list,R);//收集

}

}

/*--------------------------------------------------*/

//检测算法的正确性

void main()

{

SeqList range;

create_array(&range);

rsort(&range);

out(&range);

}

※本文中提及的排序算法在CSDN上有源码，下载地址如下：

=============================================================