北邮数据结构实验报告实验四排序含源码

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验4——排序 学生姓名： 申宇飞 班 级： 2012211103 班内序号： 03 学 号： 2012210064 日 期： 2013年12月18日

1．实验要求

使用简单数组实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2. 程序分析

第1页

北京邮电大学信息与通信工程学院

（1）、设计一个菜单，格式如下：

1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出

（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。

2.1 存储结构

2.2 关键算法分析

本程序包含了9个函数，它们分别是： （1）、直接插入排序的算法函数InsertSort（）。 void InsertSort(SqList &L) { int i,j;

for( i=2; i<=L.length;i++) {

if(L.r[i].key < L.r[i-1].key) {

L.r[0] = L.r[i]; L.r[i] = L.r[i-1];

for( j=i-2; (L.r[0].key < L.r[j].key); j--) L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; } } } （2）、希尔排序的算法函数ShellSort（）。 void ShellSort(SqList &L) {

第2页

北京邮电大学信息与通信工程学院

int i, j;

int dk = 1;//增量

while(dk <=L.length/3) dk = 3*dk+1;//增大增量 while(dk>0) {

dk /= 3;//减小增量

for (i = dk; i <=L.length; i++) { L.r[0].key = L.r[i].key; j = i;

while ((j >= dk) && (L.r[j-dk].key > L.r[0].key)) { L.r[j].key = L.r[j-dk].key; j -= dk; }

L.r[j].key = L.r[0].key; } } } （3）、冒泡排序算法函数BubbleSort（）。 void BubbleSort(SqList &L) { int i,j;

for(i=0;i

int flag = 1;

for(j=0;j L.r[j+1].key) {

flag = 0; int temp;

temp = L.r[j].key;

L.r[j].key = L.r[j+1].key; L.r[j+1].key = temp; }

//若无交换说明已经有序 if(flag==1) break; } } （4）、快速排序的算法函数Partition（）。 void BubbleSort(SqList &L) { int i,j;

for(i=0;i

第3页

北京邮电大学信息与通信工程学院

int flag = 1;

for(j=0;j L.r[j+1].key) {

flag = 0; int temp;

temp = L.r[j].key;

L.r[j].key = L.r[j+1].key; L.r[j+1].key = temp; }

//若无交换说明已经有序 if(flag==1) break; } } （5）、选择排序算法函数SelectSort（）。 void SelectSort(SqList &L) {

int min; int j;

for (int i = 0; i

min = L.r[i].key;

for (int k = i; k < L.length; k++) { // 在R[i..n-1]中选择最小的记录 if (L.r[k].key < min) {

min = L.r[k].key ; j = k; } }

if (i != j)

{ // 与第i个记录交换 int temp = L.r[i].key; L.r[i].key = L.r[j].key; L.r[j].key = temp; } } } （6）、堆排序算法函数HeapAdjust（）。 void HeapAdjust(HeapType &H,int s,int m) 第6/10页

//堆调整，将记录调整为小顶堆 int j; RedType rc = H.r[s];//暂时存储根结点

第4页