实验六：排序算法的设计

学校代码： 10128 学 号： 201220905048

《数据结构》实验报告

（

题 目：排序算法的设计 学生姓名：孙跃 学 院：理学院 系 别：数学系

专 业：信息与计算科学 班 级：信计12-2班 任课教师：杜雅娟

二 〇 一 四 年 十 一 月

一、实验目的

1.掌握排序算法；

2.提高学生的分析问题和解决问题的实际能力。 二、实验内容

1、实现直接插入排序的算法； 2、实现希尔排序的算法； 3、实现起泡排序的算法； 4、实现快速排序的算法； 5、实现堆排序的算法。 三、实验程序

1、首先建立三个公用文件 c1.h

#include #include #include #include #include #include #include #include #include #include //状态代码 #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int Boolean;

1

c9.h

#define EQ(a,b)((a)==(b)) #define LT(a,b)((a)<(b)) #define LQ(a,b)((a)<=(b)) c10-1.h

#define MAXSIZE 20 typedef int KeyType; struct RedType {

KeyType key; InfoType otherinfo; };

struct SqList {

RedType r[MAXSIZE+1]; int length; };

2、插入排序

在同一文件夹中建立如下5个文件：c1.h ,c9.h ,c10-1.h ,bo10-1.cpp ,algo10-1.cpp.对algo10-1.cpp进行编译、构建和运行。 bo10-1.cpp

void InsertSort(SqList &L) { int i,j;

for(i=2;i<=L.length;++i) if LT(L.r[i].key,L.r[i-1].key) {

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

2

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0]; } }

void BInsertSort(SqList &L) {

int i,j,m,low,high; for(i=2;i<=L.length;i++) {

L.r[0]=L.r[i]; low=1;high=i-1; while(low<=high) {

m=(low+high)/2;

if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }

for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } }

3

algo10-1.cpp #include\typedef int InfoType; #include\#include\#include\void print(SqList L) { int i;

for(i=1;i<=L.length;i++)

printf(\printf(\}

#define N 8 void main() {

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l1,l2; int i;

for(i=0;i

l1.r[i+1]=d[i];

l1.length=N; l2=l1;

printf(\排序前:\\n\

print(l1);

InsertSort(l1);

printf(\直接插入排序后:\\n\

print(l1);

4

BInsertSort(l2);

printf(\折半插入排序后:\\n\print(l2); }

3、希尔排序

在同一文件夹中建立如下4个文件：c1.h ,c9.h ,c10-1.h ,algo10-3.cpp.对algo10-3.cpp进行编译、构建和运行。

algo10-3.cpp

//algo10-3.cpp 希尔排序 #include typedef int InfoType; #include\#include\

void ShellInsert(SqList &L,int dk) { int i,j;

for(i=dk+1;i<=L.length;++i) if LT(L.r[i].key,L.r[i-dk].key) {

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

for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)

L.r[j+dk]=L.r[j];

L.r[j+dk]=L.r[0];

} }

5

void print(SqList L) { int i;

for(i=1;i<=L.length;i++)

printf(\

printf(\}

void printl(SqList L) { int i;

for(i=1;i<=L.length;i++)

printf(\

printf(\}

void ShellSort(SqList &L,int dlta[],int t) { int k;

for(k=0;k

ShellInsert(L,dlta[k]);

printf(\第%d趟排序结果:\ print(L); } }

6

#define N 10 #define T 3 void main() {

RedType

d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}}; }

4、起泡排序

在同一文件夹中建立如下2个文件：c1.h ,algo10-4cpp.对algo10-4.cpp进行编译、构建和运行。 algo10-4.cpp #include \#define N 8

void bubble_sort(int a[],int n) { int i,j,t; Status change;

7

SqList l; int dt[T]={5,3,1}; for(int i=0;i

l.r[i+1]=d[i];

l.length=N; printf(\排序前:\print(l); ShellSort(l,dt,T); printf(\排序后:\printl(l);

for(i=n-1,change=TRUE;i>1&&change;--i) {

change=FALSE; for(j=0;j

void print(int r[],int n) { int i;

for(i=0;i

printf(\ if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; change=TRUE; }

printf(\}

void main() { }

8

int d[N]={49,38,65,97,76,13,27,49}; printf(\排序前:\\n\print(d,N); bubble_sort(d,N); printf(\排序后：\\n\print(d,N);

5、快速排序

在同一文件夹中建立如下4个文件：c1.h ,c10-1.h ,bo10-2.cpp ,algo10-5.cpp.对algo10-5.cpp进行编译、构建和运行。

bo10-2.cpp

void QSort(SqList &L,int low,int high) { }

void QuickSort(SqList &L) { }

void print(SqList L) { }

9

int pivotloc; if(low

pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high);

QSort(L,1,L.length);

int i;

for(i=1;i<=L.length;i++)

printf(\

printf(\

algo10-5.cpp #include typedef int InfoType; #include\

int Partition(SqList &L,int low,int high) { }

#include\#define N 8 void main() {

RedType t; KeyType pivotkey; pivotkey=L.r[low].key; while(low

while(low=pivotkey)

--high;

t=L.r[low]; L.r[low]=L.r[high]; L.r[high]=t;

while(low

++low;

t=L.r[low]; L.r[low]=L.r[high]; L.r[high]=t;

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l;

10

}

int i;

for(i=0;i

l.r[i+1]=d[i];

l.length=N; printf(\排序前:\\n\print(l); QuickSort(l); printf(\排序后:\\n\print(l);

6、堆排序

在同一文件夹中建立如下4个文件：c1.h ,c10-1.h ,c9.h ,algo10-9.cpp.对algo10-9.cpp进行编译、构建和运行。

algo10-9.cpp. //algo10-9.cpp #include typedef int InfoType; #include\#include\typedef SqList HeapType;

void HeapAdjust(HeapType &H,int s,int m) {

RedType rc; int j; rc=H.r[s];

for(j=2*s;j<=m;j*=2)

11

{

if(j

++j;

if(!LT(rc.key,H.r[j].key))

break;

H.r[s]=H.r[j]; s=j; } H.r[s]=rc; }

void HeapSort(HeapType &H) {

RedType t; int i;

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

HeapAdjust(H,i,H.length);

for(i=H.length;i>1;--i) { t=H.r[1]; H.r[1]=H.r[i]; H.r[i]=t;

HeapAdjust(H,1,i-1); } }

void print(HeapType H) { int i;

for(i=1;i<=H.length;i++)

12

printf(\

printf(\}

#define N 8 void main() {

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; HeapType h; int i;

for(i=0;i

h.r[i+1]=d[i];

h.length=N; }

printf(\排序前：\\n\print(h); HeapSort(h); printf(\排序后\\n\print(h);

13

四、实验结果

1、插入排序

2、希尔排序

3、起泡排序

14

4、快速排序

5、堆排序

五、实验总结

本次排序算法的设计实验，让我对课上所学的插入排序、希尔排序、起泡排序、快速排序和堆排序有了更加深入的掌握，并应用到程序设计当中，通过实践，弥补了课上所学的不足。

同时，本实验作为《数据结构》实验课程的最后一个实验，到目前为止，我们一起完成了抽象数据类型的表示和实现、线性表的链式表示和实现、二叉树遍历算法的设计、图的顺序存储表示和实现、查找算法的设计和本次排序算法的设计共六个实验，通过这一系列实验，既锻炼了我们的实际动手能力，又对课堂知识进行了巩固和提高，为未来的继续学习打下了坚实的基础。

15

4、快速排序

5、堆排序

五、实验总结

本次排序算法的设计实验，让我对课上所学的插入排序、希尔排序、起泡排序、快速排序和堆排序有了更加深入的掌握，并应用到程序设计当中，通过实践，弥补了课上所学的不足。

同时，本实验作为《数据结构》实验课程的最后一个实验，到目前为止，我们一起完成了抽象数据类型的表示和实现、线性表的链式表示和实现、二叉树遍历算法的设计、图的顺序存储表示和实现、查找算法的设计和本次排序算法的设计共六个实验，通过这一系列实验，既锻炼了我们的实际动手能力，又对课堂知识进行了巩固和提高，为未来的继续学习打下了坚实的基础。

15

本文来源：https://www.bwwdw.com/article/6gud.html