数据结构实验 排序

排序实验日志

实验题目：

排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

1．程序代码

#include"stdio.h"

#include"stdlib.h"

#define Max 100 //假设文件长度

typedef struct{ //定义记录类型

int key; //关键字项

}RecType;

typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵

int n; //顺序表实际的长度

//==========直接插入排序法======

void InsertSort(SeqList R)

{ //对顺序表R中的记录R[1‥n]按递增序进行插入排序

int i,j;

for(i=2;i<=n;i++) //依次插入R[2]，……，R[n]

if(R[i].key

{ //若R[i].key大于等于有序区中所有的keys，则R[i]留在原位

R[0]=R[i];j=i-1; //R[0]是R[i]的副本

do { //从右向左在有序区R[1‥i-1]中查找R[i] 的位置

R[j+1]=R[j]; //将关键字大于R[i].key的记录后移

j--; }

while(R[0].key

R[j+1]=R[0]; //R[i]插入到正确的位置上

}//endif

}

//==========冒泡排序=======

typedef enum{FALSE,TRUE} Boolean; //FALSE为0，TRUE为1

void BubbleSort(SeqList R) { //自下向上扫描对R做冒泡排序

int i,j;

Boolean exchange; //交换标志

for(i=1;i

exchange=FALSE; //本趟排序开始前，交换标志应为假

for(j=n-1;j>=i;j--) //对当前无序区R[i‥n] 自下向上扫描

if(R[j+1].key

R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元

R[j+1]=R[j];

R[j]=R[0];

exchange=TRUE; //发生了交换，故将交换标志置为真

}

if(! exchange) //本趟排序未发生交换，提前终止算法

return;

}// endfor（为循环）

}

//1.========一次划分函数=====

int Partition(SeqList R,int i,int j)

{ // 对R[i‥j]做一次划分，并返回基准记录的位置

RecType pivot=R[i]; //用第一个记录作为基准

while(i

while(i=pivot.key) //基准记录pivot相当与在位置i上

j--; //从右向左扫描，查找第一个关键字小于pivot.key的记录R[j] if(i

R[i++]=R[j]; //交换R[i]和R[j]，交换后i指针加1

while(i

i++; //从左向右扫描，查找第一个关键字小于pivot.key的记录R[i] if(i pivot.key，则

R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1

}

R[i]=pivot; //此时，i=j，基准记录已被最后定位

return i; //返回基准记录的位置

}

//2.=====快速排序===========

void QuickSort(SeqList R,int low,int high)

{ //R[low..high]快速排序

int pivotpos; //划分后基准记录的位置

if(low

pivotpos=Partition(R,low,high); //对R[low..high]做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); //对左区间递归排序

QuickSort(R,pivotpos+1,high); //对右区间递归排序

}

}

//======直接选择排序========

void SelectSort(SeqList R)

{

int i,j,k;

for(i=1;i

k=i;

for(j=i+1;j<=n;j++) //在当前无序区R[i‥n]中选key最小的记录R[k]

if(R[j].key

k=j; //k记下目前找到的最小关键字所在的位置

if(k!=i) { // //交换R[i]和R[k]

R[0]=R[i];R[i]=R[k];R[k]=R[0];

} //endif

} //endfor

}

//==========大根堆调整函数=======

void Heapify(SeqList R,int low,int high)

{ // 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质int large; //large指向调整结点的左、右孩子结点中关键字较大者

RecType temp=R[low]; //暂存调整结点

for(large=2*low; large<=high;large*=2){ //R[low]是当前调整结点

//若large>high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子

if(large

large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者if(temp.key>=R[large].key) //temp始终对应R[low]

break; //当前调整结点不小于其孩子结点的关键字，结束调整

R[low]=R[large]; //相当于交换了R[low]和R[large]

low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置}

R[low]=temp; //将被调整结点放入最终位置上

}

//==========构造大根堆==========

void BuildHeap(SeqList R)

{ //将初始文件R[1..n]构造为堆

int i;

for(i=n/2;i>0;i--)

Heapify(R,i,n); //将R[i..n]调整为大根堆

}

//==========堆排序===========

void HeapSort(SeqList R)

{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元

int i;

BuildHeap(R); //将R[1..n]构造为初始大根堆

for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。

R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换

Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。