北邮数据结构第四次实验题目一排序

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验四 排序（题目1）姓 名： 班 级： 班内序号： 学 号：1实验要求实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对2的结果进行分析，验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确

2、性。2. 程序分析2.1 存储结构程序采用的存储机构是顺序存储，如下图所示：a0a1a2a3a4a5a6a72.2 关键算法分析 2.2.1 插入排序插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C+描述过程如下：将待插入纪录赋值给哨兵r0：r0=ri;从后向前进行顺序查找：for(j=i-1;r0<rj;j-);元素后插：rj+1=rj;插入记录：rj+1=rj;void InsertSort(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器for(int i=2;i<=n;i+)if

3、(ri<ri-1)r0=ri;int j=i-1;for(;r0<rj;j-) /边查找，边后移rj+1=rj;move+; comp+; /循环中移动计数器+comp+; /比较计数器+rj+1=r0;move+; /移动计数器+comp+; /比较计数器+cout<<"本次直接插入排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<

4、;<endl;性能分析： 原序列正序时直接插入排序达到最好的时间性能，比较次数为n-1，移动次数为0。原序列逆序时直接插入排序达到最差时间性能，比较次数为，移动次数为。 直接插入排序的平均时间复杂度为，空间复杂度为。 直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。 2.2.2 希尔排序 希尔排序的基本方法是将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。希尔排序的整个过程如下：void ShellInsert(int r,int n)int comp=0; /比较次数计数器int move=0; /

5、移动次数计数器for(int d=n/2;d>=1;d=d/2) /以d为增量在子序列中进行插入排序for(int i=d+1;i<=n;i+) /一趟希尔排序if(ri<ri-d)r0=ri;move+; /移动计数器+int j=i-d;for(;j>0&&r0<rj;j=j-d) /每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序rj+d=rj;comp+;move+; comp+; /比较计数器+ rj+d=r0;move+; /移动计数器+ comp+;/比较计数器+ cout<<"本次希尔排序数据

6、长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;希尔排序的时间复杂度在和之间，空间复杂度为，是一种不稳定的排序算法。 2.2.3 冒泡排序 冒泡排序的基本思想是，两两比较相邻的元素，如果反序，则交换位置，知道没有反序的元素为止。具体描述如下：void BubbleSort(int r,int n)int comp=0; /比较次数计数器int move=

7、0; /移动次数计数器int pos=n; /最后一次比较发生的地址while(pos!=0)int bound=pos; /比较的边界pos=0;for (int i=1;i<bound;i+)if (ri>ri+1) /相邻元素比较r0=ri;ri=ri+1;ri+1=r0; /若逆序，则交换move+=3;pos=i;comp+;comp+;cout<<"本次起泡排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较

8、："<<comp<<"次"<<endl;性能分析： 原序列正序时冒泡排序达到最好的时间性能，比较次数为n-1，移动次数为0。原序列逆序时达到最差时间性能，比较次数为，移动次数为。平均时间复杂度为，空间复杂度为。冒泡排序是一种稳定的排序算法。 2.2.4 快速排序 快速排序是冒泡排序的改进算法，快速排序元素的比较和移动是从两端向中间进行的，因而元素移动的距离较远。快速排序的基本思想是，在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分

9、区重复上述过程直到整个序列有序。经过优化改进的快速排序算法如下： /一趟快速排序static int Ecomp=0; /比较次数static int Emove=0; /移动次数int Qpass=0; /快速排序次数int Partion(int r,int first,int end)int i=first;int j=end;int pivot=ri; /选取基准元素Emove+;while(i<j)while(i<j&&rj>=pivot) /右侧扫描j-;Ecomp+;Ecomp+; /从右开始扫描找到第一个小于轴值的数ri=rj;Emove+;w

10、hile(i<j&&ri<=pivot) /左侧扫描i+;Ecomp+;Ecomp+; /从左边开始找到第一个大于轴值的数rj=ri;Emove+;ri=pivot;Emove+;return i;/完整快速排序void QSort(int r,int i,int j)/递归直到序列有序 static const int n=j;if(i<j)int pivotloc=Partion(r,i,j);Qpass+;QSort(r,i,pivotloc-1);QSort(r,pivotloc+1,j);if(Qpass=n)cout<<"本次

11、快速排序数据长度为："<<j<<" 移动："<<Emove<<"次"<<" 比较："<<Ecomp<<"次"<<endl; 性能分析：快速排序的时间复杂度为，栈的深度为。快速排序是一种不稳定的排序方法。 2.2.5 简单选择排序 简单选择排序的基本思想是：第1趟，在待排序纪录r1n中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2n中选出最小的记录，将它与r2交换以此类推，第i趟将待排序记录rin中选出

12、关键码最小的记录，与ri交换，使有序序列不断增长直到全部排序完毕。第i趟排序的过程如下：假设index是最小的：int index=i;查找最小的记录：for(int j=i+1;j<=n;j+) if(rj<rindex) index=j; 若第一个就是最小元素，则不用交换，否则交换，r0为临时空间：void SelectSort(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器for(int i=1;i<n;i+) /n-1趟排序int index=i; /查找最小记录的位置indexfor(int j=i+1;j&

13、lt;=n;j+)if(rj<rindex)index=j;comp+;if(index!=i) /若第一个就是最小记录的元素，则不用交换r0=ri;ri=rindex;rindex=r0; /利用人r0作为临时空间交换记录 move+=3;cout<<"本次选择排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;性能分析

14、：简单选择排序是移动次数最少的算法，当原序列为正序时，比较次数为，移动次数为0；当原始序列为逆序时，比较次数为，移动次数为；平均情况下的时间复杂度为，空间复杂度为。简单选择排序是不稳定的。2.3 性能比较排序方法平均时间复杂度辅助空间稳定性直接插入排序稳定希尔排序不稳定冒泡排序稳定快速排序不稳定简单选择排序不稳定3. 程序运行结果 测试主函数流程：开 始构造正序、逆序、随机序列 对正序序列使用5种排序方法 对逆序序列使用5种排序方法 对随机序列使用5种排序方法结 束 测试结论：程序运行的结果与理论分析基本一致。测试结果：随机输入：顺序输入：逆序输入：代码：/ 排序.cpp : 定义控制台应用程

15、序的入口点。/#include "stdafx.h"#include<windows.h>#include<iostream>using namespace std;/直接插入排序void InsertSort(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器for(int i=2;i<=n;i+)if(ri<ri-1)r0=ri;int j=i-1;for(;r0<rj;j-) /边查找，边后移rj+1=rj;move+; comp+; /循环中移动计数器+comp+; /比

16、较计数器+rj+1=r0;move+; /移动计数器+comp+; /比较计数器+cout<<"本次直接插入排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;/希尔排序void ShellInsert(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器for(int d=n

17、/2;d>=1;d=d/2) /以d为增量在子序列中进行插入排序for(int i=d+1;i<=n;i+) /一趟希尔排序if(ri<ri-d)r0=ri;move+; /移动计数器+int j=i-d;for(;j>0&&r0<rj;j=j-d) /每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序rj+d=rj;comp+;move+; comp+; /比较计数器+ rj+d=r0;move+; /移动计数器+ comp+;/比较计数器+ cout<<"本次希尔排序数据长度为："<<

18、n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;/起泡排序void BubbleSort(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器int pos=n; /最后一次比较发生的地址while(pos!=0)int bound=pos; /比较的边界pos=0;for (int i=1;i<bound;i+)if (ri>

19、;ri+1) /相邻元素比较r0=ri;ri=ri+1;ri+1=r0; /若逆序，则交换move+=3;pos=i;comp+;comp+;cout<<"本次起泡排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;/一趟快速排序static int Ecomp=0; /比较次数static int Emove=0; /移动次数

20、int Qpass=0; /快速排序次数int Partion(int r,int first,int end)int i=first;int j=end;int pivot=ri; /选取基准元素Emove+;while(i<j)while(i<j&&rj>=pivot) /右侧扫描j-;Ecomp+;Ecomp+; /从右开始扫描找到第一个小于轴值的数ri=rj;Emove+;while(i<j&&ri<=pivot) /左侧扫描i+;Ecomp+;Ecomp+; /从左边开始找到第一个大于轴值的数rj=ri;Emove+;ri

21、=pivot;Emove+;return i;/完整快速排序void QSort(int r,int i,int j)/递归直到序列有序 static const int n=j;if(i<j)int pivotloc=Partion(r,i,j);Qpass+;QSort(r,i,pivotloc-1);QSort(r,pivotloc+1,j);if(Qpass=n)cout<<"本次快速排序数据长度为："<<j<<" 移动："<<Emove<<"次"<<

22、;" 比较："<<Ecomp<<"次"<<endl;/简单选择排序void SelectSort(int r,int n)int comp=0; /比较次数计数器int move=0; /移动次数计数器for(int i=1;i<n;i+) /n-1趟排序int index=i; /查找最小记录的位置indexfor(int j=i+1;j<=n;j+)if(rj<rindex)index=j;comp+;if(index!=i) /若第一个就是最小记录的元素，则不用交换r0=ri;ri=rindex

23、;rindex=r0; /利用人r0作为临时空间交换记录 move+=3;cout<<"本次选择排序数据长度为："<<n<<" 移动："<<move<<"次"<<" 比较："<<comp<<"次"<<endl;int main()_LARGE_INTEGER time_start; /开始时间_LARGE_INTEGER time_end; /结束时间double freq; /寄存计时器

24、频率_LARGE_INTEGER f; /频率double time; /代码执行用时QueryPerformanceFrequency(&f); /获得内核频率freq=(double)f.QuadPart; /计时器频率为内核频率cout<<"请输入待排序数组（按ctrl+z结束）："<<endl;#define MAX 1000int aMAX;int bMAX=-1;int n=0;n+;a0=0;while(cin>>a+n) /输入待排序数组cout<<endl<<endl;cout<&l

25、t;"."<<endl;cout<<endl<<endl;QueryPerformanceCounter(&time_start); /获得开始时的震荡次数InsertSort(a,n); /插入排序QueryPerformanceCounter(&time_end); /获得结束时的震荡次数time=1000000*(time_end.QuadPart-time_start.QuadPart)/freq; /代码执行时间cout<<"本次插入排序用时为："<<time<&

26、lt;"微秒"<<endl;cout<<"."<<endl;QueryPerformanceCounter(&time_start); /获得开始时的震荡次数ShellInsert(a,n); /希尔排序QueryPerformanceCounter(&time_end); /获得结束时的震荡次数time=1000000*(time_end.QuadPart-time_start.QuadPart)/freq; /代码执行时间cout<<"本次希尔排序用时为："<&

27、lt;time<<"微秒"<<endl;cout<<"."<<endl;QueryPerformanceCounter(&time_start); /获得开始时的震荡次数BubbleSort(a,n); /起泡排序QueryPerformanceCounter(&time_end); /获得结束时的震荡次数time=1000000*(time_end.QuadPart-time_start.QuadPart)/freq; /代码执行时间cout<<"本次起泡排序用时为："<<time<<"微秒"<<endl;cout<<"."<<endl;QueryPerformanceCounter(&a