实验六排序算法的设计.doc

学校代码： 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 -1typedef int Status;typedef int Boolean;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 20typedef int KeyType;struct RedTypeKeyType key;InfoType otherinfo;struct SqListRedType rMAXSIZE+1;int length;2、插入排序在同一文件夹中建立如下5个文件：c1.h ,c9.h ,c10-1.h ,bo10-1.cpp ,algo10-1.cpp.对algo10-1.cpp进行编译、构建和运行。bo10-1.cppvoid InsertSort(SqList &L)int i,j;for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key)L.r0=L.ri;for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj; L.rj+1=L.r0;void BInsertSort(SqList &L)int i,j,m,low,high;for(i=2;i=L.length;i+)L.r0=L.ri;low=1;high=i-1;while(low=high+1;-j) L.rj+1=L.rj;L.rhigh+1=L.r0;algo10-1.cpp#includec1.htypedef int InfoType;#includec9.h#includec10-1.h#includebo10-1.cppvoid print(SqList L)int i;for(i=1;i=L.length;i+) printf(%d,%d),L.ri.key,L.ri.otherinfo);printf(n);#define N 8void main()RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8;SqList l1,l2;int i;for(i=0;iN;i+)l1.ri+1=di;l1.length=N;l2=l1;printf(排序前:n);print(l1);InsertSort(l1);printf(直接插入排序后:n);print(l1);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 希尔排序#includetypedef int InfoType;#includec9.h#includec10-1.hvoid ShellInsert(SqList &L,int dk)int i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk) L.rj+dk=L.rj; L.rj+dk=L.r0; void print(SqList L) int i; for(i=1;i=L.length;i+) printf(%4d,L.ri.key); printf(n);void printl(SqList L) int i; for(i=1;i=L.length;i+) printf(%d,%d),L.ri.key,L.ri.otherinfo); printf(n);void ShellSort(SqList &L,int dlta,int t) int k; for(k=0;kt;+k) ShellInsert(L,dltak); printf(第%d趟排序结果:,k+1); print(L); #define N 10#define T 3void main()RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8,55,9,4,10;SqList l;int dtT=5,3,1;for(int i=0;i1&change;-i) change=FALSE; for(j=0;jaj+1) t=aj; aj=aj+1; aj+1=t; change=TRUE; void print(int r,int n) int i; for(i=0;in;i+) printf(%4d,ri); printf(n);void main()int dN=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.cppvoid QSort(SqList &L,int low,int high)int pivotloc;if(lowhigh)pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)QSort(L,1,L.length);void print(SqList L)int i;for(i=1;i=L.length;i+)printf(%d,%d),L.ri.key,L.ri.otherinfo);printf(n);algo10-5.cpp#includetypedef int InfoType;#includec10-1.hint Partition(SqList &L,int low,int high)RedType t;KeyType pivotkey;pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;t=L.rlow;L.rlow=L.rhigh;L.rhigh=t;while(lowhigh&L.rlow.key=pivotkey)+low;t=L.rlow;L.rlow=L.rhigh;L.rhigh=t;return low;#includebo10-2.cpp#define N 8void main()RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8;SqList l;int i;for(i=0;iN;i+)l.ri+1=di;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#includetypedef int InfoType;#includec9.h#includec10-1.htypedef SqList HeapType;void HeapAdjust(HeapType &H,int s,int m) RedType rc; int j; rc=H.rs; for(j=2*s;j=m;j*=2) if(j0;-i) HeapAdjust(H,i,H.length); for(i=H.length;i1;-i) t=H.r1; H.r1=H.ri; H.ri=t; HeapAdjust(H,1,i-1); void print(HeapType H) int i; for(i=1;i=H.length;i+) printf(%d,%d),H.ri.key,H.ri.otherinfo); printf(n);#define N 8void main()RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8;HeapType h;int i;for(i=0;iN;i+)h.ri+1=di; h.length=N;printf(排序前：n);print(h);HeapSort(h);printf(排序后n);print(h);四、实验结果 1、插入排序2、希尔排序 3、起泡排序 4、快速排序 5、堆排序五、实验总结本次排序算法的设计实验，让我对课上所学的插入排序、希尔排序、起