数据结构实验排序算法C++实现

实验三排序姓名：班级：学号：1.实验要求1.1实验目的通过选择下面题目，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。1.2实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main（）函数测试线性表的正确性。2程序分析与关键代码2.1存储结构存储结构：一维数组2.2关键算法分析1．直接插入排序：数组分为有序区与无序区，初始时首个元素为有序。从第二个元素开始，每个元素一趟，顺序查找获得插入点。一趟实现，将待插入记录赋值给哨兵r[0],从后向前进行顺序查找，元素后移。代码实现if(r[i]〈r[i-1])//若r[i]就是最大的元素，则直接进行下一趟排序{r[0]=r[i];//待插入元素赋值给r[0]r[i]=r[iT];for(intj=i-2;r[0]〈r[j];j--)//从后向前进行顺序查找，元素后移r[j+1]=r[j];r[j+1]=r[0];2.希尔排序：将数组分成两份，将第一份数组的元素与哨兵比较，若其大于哨兵，将其值赋给哨兵，哨兵与第二份数组元素比较，将较大的值赋给第二份数组，循环进行，将数组拆分。关键代码for(inti=d+1;i〈=n;i++) //一趟希尔排序{if(r[i]〈r[i-d]){r[0]=r[i];intj;for(j=i-d;j>0&&r[0]<r[j];j=j-d){r[j+d]=r[j];r[j+d]=r[0];3.改进的冒泡排序：排序过程分为有序区与无序区，一趟冒泡排序将一个元素由无序区添加到有序区，初试有序区为空，将无序区由前向后依次将相邻元素关键码进行比较，正序不变，反序交换，关键码大的逐渐后移，重复比较，直至结尾。为去除对无序区中部分有序元素的无用比较，将前一趟最后交换位置定为pos，若前一趟排序没有元素交换，即排好序，排序算法结束。关键代码：intpos=n;while(pos!=0){intbound=pos;//将前一趟最后交换位置定为pos，即无序元素范围pos=0;//设置本趟排序元素交换起始位置for(inti=1;i<bound;i++){if(r[i]>r[i+1])//相邻比较{r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];//交换pos=i;//记录本次交换位置}}4．快速排序：选取轴值，将排序元素分为两个区，左侧关键码小于轴值，右侧大于轴值，在各个小分区重复上述过程，直至有序。选取轴值，比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较。否则后面元素赋给前面元素，若后指针元素小于标准值，前指针后移，重新比较，否则前面元素赋给后面元素。左右侧如此扫描，重复，直至左右侧值相等，排序结束。代码实现一趟快排intSORT::Partion(intr[],intfirst,intend)//一趟快排{inti=first; //分区的左界intj=end; //分区的右界intpivot=r[i];//保存第一个元素，作为基准元素while(i<j){while((i<j)&&(r[j]>=pivot))//右侧扫描，寻找<pivot的元素前移{j--;Cnum++;}r[i]=r[j];while((i<j)&&(r[i]<=pivot))//左侧扫描，寻找>pivot的元素后移Cnum++;r[j]=r[i];}r[i]=pivot;//将轴值移动到i二j的位置returni;//返回分区的分界值i}5.简单选择排序：仍将待排序数列分为有序区与无序区，一趟扫描，获得数组中最小的元素，序区中(即将最小数据与第一个数据交换，将有序区放置在数组前部分。序区数据，每次获得最小的数据，并置于有序区中。扫描数组，交换，为关键算法。代码实现一趟排序：intindex=i; //查找最小记录的位置indexfor(intj=i+1;j<=n;j++){compare++;if(r[j]<r[index])将其置于有则不用交换if(index!=i)//将其置于有则不用交换if(index!=i)//若第一就是最小元素，r[0]=r[i];r[i]=r[index];r[index]=r[0];}6.堆排序：在简单选择排序一趟结束时，堆排序能够保留其比较结果，减少比较次数，提高排序效率。实现方法需建立大根堆或者小根堆，通过对建成的堆进行排序。关键算法为建堆，排序，如小根堆。生成小跟堆：while(j<=m){if(j<m&&r[j]>r[j+1]){j++;}if(r[i]<r[j]){break;}else{intx;x=r[i];r[i]=r[j];r[j]=x;i=j;j=2*i;}}将堆的根节点移至数组的最后：x=r[1];r[1]=r[n-i+1];r[n-i+1]=x;去掉已做过根节点的元素继续生成小根堆：sift(r,1,n-i,x,y);数组倒置输出:for(inti=n;i>0;i--)cout<<r[i]<<"";堆排序for(inti=n/2;i>=1;i--)//建堆Sift(r,i,n);for(inti=n;i>1;i--) //堆排序{r[0]=r[1];r[1]=r[i];r[i]=r[0]; //输出堆顶元素Sift(r,1,i-1);//重建堆各排序算法时间复杂度插入排序O(n2)希尔排序O（nlog2n~n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）4.测试结果5.总结调试总是出错，测试函数写得不好，不怎么会写，几个选作的最后还是没调出来。心得体会：学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，在数组情况下，差距不很明显，不同的排序方法移动次数比较次数和所用时间都是有所区别的。学会各种算法使用的情况下一步的改进：改进计数器，寻找其他排序方式。5.附原代码#include<iostream>usingnamespacestd;intCnum=0;//统计比较intMnum=0;//统计移动classSORTintintintintprivate:compare;//比较次数move;//移动次数public:void

n);

voidInsertSort(intr[],iShelllnsert(intr[],in)voidBubbleSort(intr[],n);intPartion(intr[],intfirst,intend);//直接插入排序//希尔排序//冒泡排序//一趟快排voidQsort(intr[],inti,intj);//快速排序voidSelectSort(intr[],intn);voidSift(intr[],intk,intm);voidHeapSort(intr[],intn);//选择排序//建堆//堆排序////插入排序voidSORT::InsertSort(intr[],intn)compare=0;move=0;for(inti=2;i<=n;i++)if(r[i]<r[i-1])r[0]=r[i];move++;r[i]=r[i-1];move++;intj;for(j=i-2;r[0]<r[j];j--)compare++;r[j+1]=r[j];move++;}++compare;r[j+1]=r[0];move++;}++compare;}for(inti=1;i<=n;i++)cout<<r[i]<<"";cout<<"比较次数为"<<compare<<";移动次数为"<<move<<";";voidSORT::ShellInsert(intr[],intn)//希尔排序{compare=0;move=0;for(intd=n/2;d>=1;d=d/2){for(inti=d+1;i<=n;i++)if(r[i]<r[i-d]){move++;r[0]=r[i];intj;for(j=i-d;j>0&&r[0]<r[j];j=j-d){r[j+d]=r[j];move++;}compare++;r[j+d]=r[0];move++;}compare++;}}for(inti=1;i<=n;i++)cout<<r[i]<<"";cout<<"比较次数为"<<compare<<";移动次数为"<<move<<";";

voidSORT::BubbleSort(intr[],intn){//冒泡排序改进compare//冒泡排序改进move=0;intpos=n;while(pos!=0){intbound=pos;pos=0;for(inti=1;i<bound;i++){compare++;if(r[i]>r[i+1]){r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];pos=i;move=move+3;//交换for(inti=1;i<=n;i++)cout<<r[i]<<"";cout<<"比较次数为"<<compare<<";移动次数为"<<move<<";";}intSORT::Partion(intr[],intfirst,intend)//一趟快排{inti=first;//分区的左界intj=end; //分区的右界intpivot=r[i];//保存第一个元素，作为基准元素while(i<j){while((i<j)&&(r[j]>=pivot))//右侧扫描，寻找<pivot的元素前移{j--;Cnum++;}r[i]=r[j];while((i<j)&&(r[i]<=pivot))//左侧扫描，寻找>pivot的元素后移{i++;Cnum++;}r[j]=r[i];}r[i]=pivot;//将轴值移动到i=j的位置returni;//返回分区的分界值i}voidSORT::Qsort(intr[],inti,intj){if(i<j){Mnum++;intpivotloc=Partion(r,i,j);Qsort(r,i,pivotloc-1);//左分区快速排序Qsort(r,pivotloc+1,j);//右分区快速排序}else{

voidSORT::SelectSort(intr[],intn)//简单选择排序//简单选择排序move=0;for(inti=1;i<ni++)//n-1趟排序index{index//查找最小记录的位置intindex//查找最小记录的位置for(intj=i+1;j<=n;j++){compare++;if(r[j]<r[index])index=j;}if(index!=i)//若就是第最则不用交换{r[0]=r[i];r[i]=r[indre[xi]n;dex]=r[0];//利用r[0]，作为临时空间交换记录move+=3;for(inti=1;i<=n;i++)cout<<r[i]<<"";cout<<"比较次数为"<<compare<<";移动次"<<move<<"数为}voidSORT::Sift(intr[],intk,intm) //建堆{inti=k,j=2*i;while(j<=m){if(j<m&&r[j]<r[j+1])j++;if(r[i]>=r[j])break;else{r[0]=r[i];r[i]=r[j];r[j]=r[0];}j=2*i;}}voidSORT::HeapSort(intr[],intn){for(inti=n/2;i>=1;i--)//建堆Sift(r,i,n);for(inti=n;i>1;i--) //堆排序//输出堆顶

元素{r[0]=r[1];r[1]=//输出堆顶

元素}}intmain()//测试主函数{intr1[10000],r2[10000],r3[10000];intR[10000];chary;intj=0;cout<<"请输入元素个数："<<endl;cin>>j;cout<<"请输入将要排序的元素（正序）"<<endl;for(inti=1;i<=j;i++){cin>>r1[i];}cout<<"请输入将要排序的元素(逆序)"<<endl;for(inti=1;i<=j;i++){cin>>r2[i];}cout<<"请输入将要排序的元素(乱序)："<<endl;for(inti=1;i<=j;i++){cin>>r3[i];}cout<<endl;SORTl;for(inti=1;i<=j;i++){R[i]=r1[i];cout<<"直接插入排序正序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r2[i];}cout<<"直接插入排序逆序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r3[i];}cout<<"直接插入排序乱序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r1[i];}cout<<"希尔排序正序输出结果：cout<<endl;";l.InsertSort(R,j);";l.InsertSort(R,j);";l.InsertSort(R,j);";l.ShellInsert(R,j);for(inti=1;i<=j;i++)R[i]=r2[i];}cout<<"希尔排序逆序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r3[i];}cout<<"希尔排序乱序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r1[i];}cout<<"冒泡排序正序输出结果：cout<<endl;for(inti=1;i<=j;i++){R[i]=r2[i];}cout《《en冒l泡排序逆序输出结9果：";l.ShellInsert(R,j);";l.ShellInsert(R,j);";l.BubbleSort(R,j);";l.BubbleSort(R,j);for(inti=1;i<=j;i++){R[i]=r3[i];}cout<<"冒泡排序乱序输出结果：";l.BubbleSort(R,j);cout<<endl;for(inti=1;i<=j;i++){R[i]=r1[i];}cout<<"快速排序正序输出结果：";l.Qsort(R,1,j);for(intk=1;k