《数据结构 内部排序实验》由会员分享，可在线阅读，更多相关《数据结构 内部排序实验（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法课程实验报告实验六：排序实践姓名：沈靖雯班级：14 信科二班学号：2014326601094实验六 排序实践【实验内容】 实现各排序算法并进行性能比较【实验目的】掌握各排序算法的实现方法，并分析各排序算法的时间和空间性能。【问题描述】 实现各排序算法，必须实现希尔排序和快速排序算法，其他排序算法选做，并分析各算法的性能。【问题实现】 （1 ）数据结构类#define MAXSIZE 20typedef structint key;Redtype;typedef structRedtype rMAXSIZE+1;int length; SqList;（2）主要算法函数：1）.希尔排
2、序；一趟希尔插入排序代码如下，其中 dk 为前后记录位置的增量，一次希尔排序后，记录按增量 dk 有序：void ShellInsert(SqList &Q,int dk)/希尔插入排序 int i,j;for(i=dk+1;i0&(Q.r0.key0;k-=2)ShellInsert(Q,k); 2）.快速排序；快速排序是对起泡排序的一种改进。下面是一次快速排序的函数代码，其中 pivotkey 表示轴枢，用子表第一个记录做轴枢记录，函数返回新的轴枢位置：int partition(SqList &Q,int low,int high)Q.r0=Q.rlow;int pivotkey;piv
3、otkey=Q.rlow.key;while(low=pivotkey) -high;Q.rlow=Q.rhigh;while(low#include #define MAXSIZE 20typedef structint key;Redtype;typedef structRedtype rMAXSIZE+1;int length; SqList;void ShellInsert(SqList &Q,int dk)/希尔插入排序 int i,j;for(i=dk+1;i0&(Q.r0.key0;k-=2)ShellInsert(Q,k); /快速排序int partition(SqList
4、&Q,int low,int high)Q.r0=Q.rlow;int pivotkey;pivotkey=Q.rlow.key;while(low=pivotkey) -high;Q.rlow=Q.rhigh;while(low0)&(flag=1) flag=0;for(int j=1;jQ.rj+1.key) flag=1;x=Q.rj.key;Q.rj.key=Q.rj+1.key;Q.rj+1.key=x;for(int i=1;i=Q.length;i+)/一次冒泡排序输出 printf(%d ,Q.ri.key);printf(n); m-;int main() SqList Q,L,M;printf(请输入初始序列长度：n);scanf(%d,&Q.length) ;printf(请输入初始序列：n);for(int i=1;i=Q.length;i+)scanf(%d,&Q.ri) ;L=M=Q;printf(希尔排序：n);Shellsort(Q);printf(快速排序：n); QuickSort(L);printf(起泡排序：n); BubbleSort(M);
