数据结构实验报告实验名称：实验四——排序学生：XX班级：班序号：学号：日期：1．实验要求实验目的：通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

题目1：使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。

具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。

5、编写main（）函数测试各种排序算法的正确性。

2. 程序分析2.1 存储结构存储结构：数组2.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; 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(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位： mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

3、测试结论：不同的排序方法移动次数比较次数和所用时间都是有所区别的。

4. 总结调试时出现的问题及解决的方法：在调试时，开始在归并排序的时候，虽然代码编译成功，但调试出现了错误，通过逐步调试发现是由于发生了地址冲突。

因此将原本的直接调用数组改成了结构体数组，通过引用来实现归并排序，最终获得了成功心得体会：学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况下一步的改进：改进计数器，寻找其他排序方式。

附：源代码#include<iostream>using namespace std;int Cnum = 0;int Mnum = 0;class LED{private :int compare;int move;public:void InsertSort(int r[] , int n) ;//直接插入排序void ShellInsert(int r[],int n) ;//希尔排序void BubbleSort(int r[],int n);//冒泡排序void Qsort(int r[],int i,int j);//快速排序void SelectSort(int r[],int n);//选择排序void HeapSort (int r[],int n);void MergePass(int r[],int r1[],int n ,int h);int Partion(int r[] ,int first ,int end );void Sift(int r[],int k , int m);void Merge(int r[],int r1[],int s,int m,int t);};void LED::InsertSort(int r[] , int n) //插入排序{compare = 0;move = 0;for(int i=2;i<=n;i++){if(r[i]<r[i-1]){r[0]=r[i];move ++;r[i]=r[i-1];move ++;int j;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(int i=1;i<=n;i++)cout<<r[i]<<" ";cout<<"比较次数为"<<compare <<" ; 移动次数为"<<move<<" ;"; }void LED::ShellInsert(int r[],int n) //希尔排序{compare = 0;move = 0;for(int d=n/2;d>=1;d=d/2){for(int i=d+1;i<=n;i++){if(r[i]<r[i-d]){move++;r[0]=r[i];int j;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(int i=1;i<=n;i++)cout<<r[i]<<" ";cout<<"比较次数为"<<compare <<" ; 移动次数为"<<move<<" ;"; }void LED::BubbleSort(int r[],int n) //冒泡排序改进{compare = 0;move = 0;int pos = n ;while(pos != 0){int bound = pos;pos = 0;for(int i =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(int i=1;i<=n;i++)cout<<r[i]<<" ";cout<<"比较次数为"<<compare <<" ; 移动次数为"<<move<<" ;";}int LED::Partion(int r[] ,int first ,int end ){int i = first ; //分区的左界int j = end; //分区的右界int pivot = 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的位置return i; //返回分区的分界值i}void LED::Qsort(int r[],int i,int j){if(i < j){ Mnum ++;int pivotloc = Partion(r,i,j);Qsort (r,i,pivotloc -1); //左分区快速排序Qsort (r,pivotloc +1,j); // 右分区快速排序}else{}}void LED::SelectSort(int r[],int n) //简单选择排序{compare = 0;move = 0;for(int i =1 ; i <n ; i++) //n-1趟排序{int index = i; //查找最小记录的位置indexfor(int j = i + 1;j<=n;j++){compare++;if(r[j]<r[index])index = j;}if(index != i) //若第一就是最小元素，则不用交换{r[0] = r[i];r[i] = r[index];r[index] = r[0]; //利用r[0]，作为临时空间交换记录move+=3;}}for(int i=1;i<=n;i++)cout<<r[i]<<" ";cout<<"比较次数为"<<compare <<" ; 移动次数为"<<move<<" ;";}/*void LED::Sift(int r[],int k , int m){int i = 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];i = j ;j = 2* i;}}}void LED::HeapSort (int r[],int n){for(int i = n/2; i >= 1 ; i--) //建堆Sift(r,i,n);for(int i = n;i>1;i--) //堆排序{r[0] = r[1]; r[1] = r[i];r[i]= r[0]; //输出堆顶元素Sift(r,1,i-1); //重建堆}}void LED::Merge(int r[],int r1[],int s,int m,int t){int i=s;int j = m + 1;int k = s ;while(i<=m&&j<=t){if(r[i]<r[j])r1[k++] = r[i++];elser1[k++] = r[j++];}while(i<=m)r1[k++] = r[i++];while(j<=t)r1[k++] = r[j++];}void LED::MergePass(int r[],int r1[],int n ,int h) {int i = 1;while(i<=n-2*h+1){Merge (r ,r1,i,i+h-1,i+2*h-1);i+= 2*h;}if(i<n-h+1)Merge (r,r1,i,i+h-1,n);elsefor(;i<=n;i++)r1[i] = r[i];}*/void main(){int r1[10000],r2[10000],r3[10000];int R[10000];char y ;int j=0;cout<<"请输入元素个数："<<endl;cin>>j;cout<<"请输入将要排序的元素(正序)："<<endl;for(int i=1;i<=j;i++){cin>>r1[i];}cout<<"请输入将要排序的元素(逆序)："<<endl;for(int i=1;i<=j;i++){cin>>r2[i];}cout<<"请输入将要排序的元素（乱序）："<<endl;for(int i=1;i<=j;i++){cin>>r3[i];}cout<<endl;LED l;for(int i= 1;i<=j;i++){R[i]=r1[i];}cout<<"直接插入排序正序输出结果：";l.InsertSort(R,j); cout<<endl;for(int i= 1;i<=j;i++){R[i]=r2[i];}cout<<"直接插入排序逆序输出结果：";l.InsertSort(R,j); cout<<endl;for(int i= 1;i<=j;i++){R[i]=r3[i];}cout<<"直接插入排序乱序输出结果：";l.InsertSort(R,j); cout<<endl;for(int i= 1;i<=j;i++){R[i]=r1[i];}cout<<"希尔排序正序输出结果：";l.ShellInsert(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r2[i];}cout<<"希尔排序逆序输出结果：";l.ShellInsert(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r3[i];}cout<<"希尔排序乱序输出结果：";l.ShellInsert(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r1[i];}cout<<"冒泡排序正序输出结果：";l.BubbleSort(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r2[i];}cout<<"冒泡排序逆序输出结果：";l.BubbleSort(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r3[i];}cout<<"冒泡排序乱序输出结果：";l.BubbleSort(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r1[i];}cout<<"快速排序正序输出结果：";l.Qsort(R,1,j);for(int k=1;k<=j;k++)cout<<R[k]<<" ";cout<<"比较次数为"<<Cnum <<" ; 移动次数为"<<Mnum<<" ";Cnum = 0;Mnum = 0;cout<<endl;for(int i= 1;i<=j;i++){R[i]=r2[i];}cout<<"快速排序逆序输出结果：";l.Qsort(R,1,j);for(int k=1;k<=j;k++)cout<<R[k]<<" ";cout<<"比较次数为"<<Cnum <<" ; 移动次数为"<<Mnum<<" ";Cnum = 0;Mnum = 0;cout<<endl;for(int i= 1;i<=j;i++){R[i]=r3[i];}cout<<"快速排序乱序输出结果：";l.Qsort(R,1,j);for(int k=1;k<=j;k++)cout<<R[k]<<" ";cout<<"比较次数为"<<Cnum <<" ; 移动次数为"<<Mnum<<" "; cout<<endl;for(int i= 1;i<=j;i++){R[i]=r1[i];}cout<<"简单选择排序正序输出结果：";l.SelectSort(R,j);cout<<endl;for(int i= 1;i<=j;i++){R[i]=r2[i];}cout<<"简单选择排序逆序输出结果：";l.SelectSort(R,j); cout<<endl;for(int i= 1;i<=j;i++){R[i]=r3[i];}cout<<"简单选择排序乱序输出结果：";l.SelectSort(R,j); cout<<endl;}。