1数据结构实验报告内部排序班级：13软工一班学号：13131113姓名：吕蒙学号：13131116姓名：钱剑滨学号：13131142姓名：孔亚亚学号：13131144姓名：邱佃雨213软工转本1钱剑滨实验报告内部排序实验报告信息工程系13软工转本1日期2016年06月07日一、实验内容编写程序实现各种内部排序（包括：冒泡排序、插入排序、选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序），并运用这些排序对一组随机生成的数组进行排序。二、时间复杂度1．冒泡排序（O(n^2））若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。所以，冒泡排序最好的时间复杂度为。若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：冒泡排序的最坏时间复杂度为。综上，因此冒泡排序总的平均时间复杂度为。2．插入排序（O(n^2））如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。3．选择排序（O(n^2））选择排序的交换操作介于0和(n-1）次之间。选择排序的比较操作为n(n-1）/2次之间。选择排序的赋值操作介于0和3(n-1）次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。34．希尔排序希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。5．快速排序（O(n^2））无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候（设输入的表有n个元素）。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。对于有n个元素的表L[p..r]，由于函数Partition的计算时间为θ（n），所以快速排序在序坏情况下的复杂性有递归式如下：T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n)(1)用迭代法可以解出上式的解为T(n)=θ（n2）。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n）是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1(2)我们假设对于任何k
