数据结构实验报告——排序.docx

1．实验要求【实验目的】学习、实现、对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况。【实验内容】使用简单数组实现下面各种排序算法并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据比较上述排序算法中不同算法的执行时间精确到微秒（选作）4、对2和3的结果进行分析验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构存储结构：数组r1≤r2≤……≤ri-1riri+1……rn有序区无序区图8-1直接插入排序的基本思想图解插入到合适位置2.2关键算法分析//插入排序voidInsertSort(intr[]intn){intcount1=0count2=0;for(inti=2;i<n;i++){r[0]=r[i];//设置哨兵for(intj=i-1;r[0]<r[j];j--)//寻找插入位置r[j+1]=r[j];//记录后移r[j+1]=r[0];count1++;count2++;}for(intk=1;k<n;k++)cout<<r[k]<<"";cout<<endl;cout<<"比较次数为"<<count1<<"移动次数为"<<count2<<endl;}//希尔排序voidShellSort(intr[]intn){inti;intd;intj;intcount1=0count2=0;for(d=n/2;d>=1;d=d/2)//以增量为d进行直接插入排序{for(i=d+1;i<n;i++){r[0]=r[i];//暂存被插入记录for(j=i-d;j>0&&r[0]<r[j];j=j-d)r[j+d]=r[j];//记录后移d个位置r[j+d]=r[0];count1++;count2=count2+d;}count1++;}for(i=1;i<n;i++)cout<<r[i]<<"";cout<<endl;cout<<"比较次数为"<<count1<<"移动次数为"<<count2<<endl;}r1≤r2≤……≤ri-1riri+1……rn有序区无序区图8-1直接插入排序的基本思想图解插入到合适位置//起泡排序voidBubbleSort(intr[]intn){inttemp;intexchange;intbound;intcount1=0count2=0;exchange=n-1;//第一趟起泡排序的范围是r[1]到r[n]while(exchange)//仅当上一趟排序有记录交换才进行本趟排序{bound=exchange;exchange=0;for(intj=0;j<bound;j++)//一趟起泡排序{count1++;//接下来有一次比较if(r[j]>r[j+1]){temp=r[j];//交换r[j]和r[j+1]r[j]=r[j+1];r[j+1]=temp;exchange=j;//记录每一次发生记录交换的位置count2=count2+3;//移动了3次}}}for(inti=1;i<n;i++)cout<<r[i]<<"";cout<<endl;cout<<"比较次数为"<<count1<<"移动次数为"<<count2<<endl;}//快速排序一次划分intPartition(intr[]intfirstintendint&count1int&count2){inti=first;//初始化[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置图8-6快速排序的基本思想图解i