数据结构实验六

实验六排序一、 实验目的1、 掌握内部排序的基本算法；2、 分析比较内部排序算法的效率。二、 实验预习说明以下概念1、 简单排序：将一组记录按某关键字递增或递减的顺序排序。2、 希尔排序：又称“缩小增量排序”属于插入排序类的方法。3、 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。4、 堆排序：只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。三、 实验内容和要求1、编程实现直接插入排序算法。程序代码：#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("请输入待排序的记录的个数：")；//scanf("%d”,&L.length);printf(-请输入待排序的记录的关键字(整型数)：")；while(scanf("%d”,&L.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*输出顺序表*/{inti;for(i=1;i<=L.length;i++)printf("%d”,L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，需将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("\n1.简单插入排序\n");InsertSort(S);Print_Sq(S);/*printf("3.快速排序\n");QuickSort(S);Print_Sq(S);printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}2、输入待排序序列：49386597132749(以输入一个字符作为结束)1)直接插入排序运行结果(写出每一趟的状态)：TOC\o"1-5"\h\z3849 65 97 13 27 491338 49 65 97 27 491327 38 49 65 97 4913273849496597

2）堆排序运行结果（写出每一趟的状态）:3、编程实现快速排序算法。程序代码：#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("请输入待排序的记录的个数：〃)；//scanf(〃%d〃,&L.length);printf(-请输入待排序的记录的关键字(整型数)：");while(scanf(〃%d〃,&L.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*输出顺序表*/{inti;for(i=1;i<=L.length;i++)printf("%d”,L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，需将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}intPartition(Sqlist&L,intlow,inthigh){//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时//在它之前(后)的记录均不大(小)于它。KeyTypepivotkey;L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录pivotkey=L.r[low];//枢轴记录关键字while(low<high){//从表的两端交替地向中间扫描while(low<high&&L.r[high]>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(low<high&&L.r[low]<=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端}L.r[low]=L.r[0];//枢轴记录到位returnlow;//返回枢轴位置}voidQSort(Sqlist&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..high]进行快速排序intpivotloc;if(low<high){//长度大于1pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}voidQuickSort(Sqlist&L){//对顺序表L作快速排序。QSort(L,1,L.length);}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("\n1.简单插入排序\n");InsertSort(S);Print_Sq(S);printf("\n2.快速排序\n");QuickSort(S);Print_Sq(S);/*printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}输入待排序序列：49386597132749(以输入一个字符作为结束)运行结果(写出每一趟的状态)：初始关键字： 49386597132749完成一趟排序： {273813}49{976549}分别进行