实验题【实验四题目1】

数据结构实验报告

实验名称： 实验四——题目一

学生姓名： 唐文旭

班 级：2013211118

班内序号： 09

学 号： 2013210524

日 期： 2015年1月5日

1．实验要求

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

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

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

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

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

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

2.2 关键算法分析

北京邮电大学信息与通信工程学院

第2页

希尔排序又称“缩小增量排序”，是对直接插入排序的一种改进，它利用了直接插入的两个特点：1. 基本有序的序列，直接插入最快；2. 记录个数很少的无序序列，直接插入也很快。希尔排序的基本思想为：将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。

冒泡排序的基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。具体的排序过程是：将整个待排序元素划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的元素；对无序区从前向后依次将相邻元素的关键码进行比较，若反序则交换，从而使得关键码小的元素向前移，关键码大的元素向后移；重复执行前一个步骤，直到无序区中没有反序的元素。

快速排序元素的比较和移动是从两端向中间进行的。快速排序的基本思想是：在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。

简单选择排序的基本思想是：第1趟，在待排序记录r[1„n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2„n]中选出最小的记录，将它与r[2]交换；以此类推，第i 趟，在待排序记录r[i„n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

r[0]留空，初始时赋为0

2.2 关键算法分析

1、直接插入排序

自然语言描述：

（1） 将整个待排序的记录划分成有序区和无序区。有序区为待排序记录的第一个记录， 无序区为所有剩余带待排序记录。

（2） 从第二个数据开始依次插入到有序区中，直到所有记录插入完毕。 （3） 在r[0]处设置“哨兵”，记为要插入的记录r[i]，在自i-1起往前查找的过程中，同时

后移记录。

（4） 找到插入位置后，将待插入记录插入到有序表中。

（5） 重复执行（3）、（4），直到无序区中没有记录。

伪代码描述：

初始化比较次数compare =0，移动次数move =0 2. for(int i=2;i

for(j=i-1;r[0]

r[j+1]=r[j] 比较次数++；移动次数++；

r[j+1]=r[0]，移动次数++

时间复杂度：最好情况下，待排序序列为正序，每趟秩序与有序序列的最后一个纪录的关键码比较一次，移动两次记录。总的比较次数为n-1，记录移动的次数为2（n-1）。因此，时间复杂度为O （n ）。

最坏情况下，待排序序列为逆序，比较次数为(n+2)(n+1)/2，移动次数为(n+4)(n-1)/2因此，时间复杂度为O （n2）.

平均情况下，总的比较次数为n （n-1）/4，移动次数为（n+4）（n-1）/4，因此，时间复杂度

为O （n2）

2、希尔排序

自然语言描述：

（1） 假设待排序记录为n 个，先取整数d

中的前一个记录比较，在插入记录r[i]时，自r[i-d]往前查找待插入位置，在查找过程中，记录后移也是移动d 个位置。

（3） 当搜索位置j=r[j]，表示插入位置已经找到。在整个序列中，前d 个记 录分别是d 个子序列的第一个记录，所以从第d+1个记录开始插入。 （4） 再缩小d ，重复以上步骤，再对每个子序列进行直接插入排序，直到d=1，即将所有

记录放在一组进行一次直接插入排序，最终将所有记录重新排序得到有序序列。

伪代码描述：

1. 初始化比较次数compare =0，移动次数move =0

for(int d=n/2;d>=1;d=d/2)

for(int i=d+1;i

if(r[i]

r[0]=r[i]，移动次数++

for(j=i-d;i>0&&r[0]

r[j+d]=r[j] 比较次数++，移动次数++

r[j+d]=r[0]，移动次数++

时间复杂度：

希尔排序的时间性能分析是一个复杂的问题，因为它是所取增量的函数。有人在大量实验的基础上指出，希尔排序的时间性能在O （n2）和O （nlog2n ）之间

3、冒泡排序

自然语言描述：

（1） 将整个待排序的记录划分成有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量pos ，此位置之后的所有记录均已经有序。

（2） 对无序区从前向后一次将相邻记录的关键码进行比较，若反序则交换，从而使得关 键码小的记录前移，关键码大的记录后移。

（3） 每趟冒泡排序开始之前，设pos 初值为0，在该趟排序过程中，只要有记录的交换，pos 就大于0。通过pos 是否为0判断是否有记录的交换，从而判断冒泡排序是否结束。 伪代码描述：

初始化比较次数compare =0，移动次数move =0

int pos=0 2. while(pos!=0)

int bound=pos，pos=n

for(int j=1;j

if(r[j]>r[j+1])

r[0]=r[j]，r[j]=r[j+1],r[j+1]=r[0]

pos=j，move+=3

时间复杂度：

最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键妈的比较，不需要移动记录，时间复杂度为O （n ） 最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的纪录被交换到最终位置，故算法执行n-1趟，第i 趟排序执行了n-1

次关键码的比较和n-i 次记录的交换，这样，关键码的比较次数为n （n-1）/2，记录的移动次数为3n （n-1）/2平均情况下，起泡排序的时间复杂度与最坏情况同数量级。

4、快速排序

自然语言描述：

（1） 取第一个记录作为基准，设置两个参数i ，j 分别用来指示将要与基准记录进行比较 的左侧记录位置和右侧记录位置，也就是本次划分的区间。 （2） 右侧扫描过程：将基准记录与j 指向的记录进行比较，如果j 指向记录的关键码大，

则j--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[i]=r[j] （3） 左侧扫描过程：将基准记录与i 指向的记录进行比较，如果i 指向记录的关键码大，

则i--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[j]=r[i]

（4） 重复执行（2）、（3），直到i 、j 指向同一位置。 （5） r[i]=pivot （6） 返回i 的位置 伪代码描述：

int i=first; int j=end; int pivot=r[i] 2. while(i

while((i=pivot))

j--; 比较次数++

r[i]=r[j] 2.3 if(i

while((i

r[j]=r[i] 2.6 if(i

r[i]=pivot; return i ;

时间复杂度：

最好情况下，每次划分对一个记录定位后，该记录的左侧子序列和右侧子序列的长度相同。在具有n 个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需时间为O

（n ）。时间复杂度为O （nlog2n ）。 最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个纪录的子序列（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i 趟划分需要经过n-i 次关键码的比较才能找到第i 个记录的基准记录，因此总的比较次数为n （n-1）/2，记录的移动次数小于等于比较次数。因此时间复杂度为O （n2）. 平均情况下，可以用归纳法证明，其数量级也为O （nlog2n ）。

5、简单选择排序

自然语言描述：

（1） 将整个记录划分为有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量index ，记录一次比较中关键码最小的位置。

（2） 第i 趟简单选择排序的待排序区间是r[i]-r[n]，首先将index 设定为当前无序区的第一个位置，然后用r[index]与无序区中其他记录进行比较，若有比r[index]小的记录，就将index 改为这个新的最小的记录的位置。

（3） 如果index 不等于i ，则将它与无序区中第一个记录交换，有序区增加一个记录，无 序区减少一个记录。 （4） 重复（2）（3），直到无序区只剩下一个记录为止。此时所有记录已经按照从小到大

的顺序排好。 伪代码描述：

初始化比较次数compare=0，移动次数move=0

for(int i=1;i

int index=i

for(int j=i+1;j

if(r[j]

if(index!=i)

r[0]=r[i];r[i]=r[index];r[index]=r[0]

move+=3

时间复杂度：待排序序列为正序时，记录的移动次数最少，为0次。在待排序序列为逆序时，记录的移动次数最多为3（n-1）次。

无论记录的初始排列如何，关键码的比较次数相同，第i 趟排序需进行n-1次关键码的比较，而简单选择排序需进行n-1趟排序，则总的比较次数为n （n-1）/2=O（n2）。所以， 总的时间复杂度为O(n2)，这是简单选择排序最好、最坏、和平均的时间性能。

3. 程序运行结果

测试条件：

问题规模的数量级是4，正序逆序由键盘输入，随机数由随机数生成函数生成。

测试结论：

程序对不同序列的数组运用各种不同方法进行排序时均能得到正确的排序结果，同时能够给出正确的比较次数和移动次数。

4. 总结

插入排序：n*n的时间复杂度，稳定排序，原地排序。在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。

希尔排序：n*log(n)的时间复杂度， 非稳定排序，原地排序。主要思想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不是想合并那样左一半右一半。 开始

输出测试数组

进行简单插入排序 进行希尔排序

进行起泡排序 进行快速排序

进行简单选择排序 结束

开始步长为整个的长度的一半，然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后希尔排序就完成了。这个思路很好，是插入排序的升级版，我觉得他是一个特别好的排序方法了。他的缺点就是两个数可能比较多次，但效率也是很高的。

冒泡排序，n*n的时间复杂度，稳定排序，原地排序。冒泡排序的思想很不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定排序，而且好实现，所以用处也是比较多的。

选择排序，n*n的时间复杂度， 稳定排序，原地排序。选择排序就是冒泡的基本思想，从小的定位，一个一个选择，直到选择结束。和插入排序是一个相反的过程，插入是确定一个元素的位置，而选择是确定这个位置的元素。它的好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。