武汉理工大学《数据结构》课程设计说明书
初始化计数器QC=0，将i和j分别指向排序区域的最左侧和最右侧记录的位置，即i=left,j=right; 基准值 Temp=R[i] QC+1 是 J-1 若R[j]>temp且j>i 否 j>i 是 是 否 R[i]=R[j],i+1 QC+1,i+1 是 R[j]<=temp且j>i 否 i 武汉理工大学《数据结构》课程设计说明书 R[j]=R[i];j-1 否 i 6 武汉理工大学《数据结构》课程设计说明书 三．调试报告 一、对冒泡排序算法复杂度的分析 1. 算法的最好时间复杂度: 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值。冒泡排序最好的时间复杂度为O(n)。 2. 算法的最坏时间复杂度：若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值，冒泡排序的最坏时间复杂度为O(n2)。 3. 算法的平均时间复杂度为O(n2)。 4. 算法稳定性:冒泡排序是就地排序，且它是稳定的。 二、对快速插入排序算法复杂度的分析 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分共需k-1次关键字的比较。 1．最坏时间复杂度 ：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基 准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目仅仅比 划分前的无序区中记录个数减少一个。 2．最好时间复杂度 ：在最好情况下，每次划分所取的基准都是当前无序区的\中值\记录划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次O(nlgn)。 3．平均时间复杂度 ：尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，它的平均时间复杂度为O(nlgn)。 4．稳定性 ：快速排序是非稳定的。 四．经验和体会 从运行结果可以看到，快速排序在规模小的时候时间几乎为0，规模小时冒泡与快速排序时间性能差不多，在规模变大就逐渐可以看到差距，因此简单排序中快速排序最快，当文件为正序时冒泡则比较好些，由于是随机的，而且时间精度有限无法看到此情况。若文件初始状态基本有序(指正序)，则应选用冒泡或随机的快速排序 。若n较大，则应采用时间复杂度为O(nlgn)的快速排序。 通过这个实验，更加了解了这两个排序的各自的定义和特点，懂得了冒泡排序和快速排序的时间性能。知道了当n不大的时候，元素基本有序，或者分布比较随机并且有排序稳定性要求时，宜采用冒泡排序方法等等。这次实验对排序的基本排序步骤都比较清晰。 冒泡排序算法的改进设想：记住最后一次交换发生位置lastExchange的冒泡排序。在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之前的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。 快速排序算法的改进设想：由于快速排序多次因为很小的子文件而调用自身，所以可以在其长度较小时，停止使用快速排序，而使用插入排序：If (right - left <= M) InsertSort(Item, left, right) M通常取5-25，实验表明，其速度比M=1快10%以上。 7 武汉理工大学《数据结构》课程设计说明书 中间元素法：取3个元素的中间元素作为Partition的依据，而不是Item[right]，可以保证不出现最坏情况 五．源程序和运行结果 #include\#include\#include\ #include\ long Bubblesort(long R[],long n) { int flag=1; long BC=0; for(long i=1;i flag=0; for(long j=n-1;j>=i;j--) { if(R[j] long t=R[j]; R[j]=R[j-1]; R[j-1]=t; flag=1; BC++; } } } return BC; } long Bubblesortcompare(long R[],long n) { int flag=1; long BC=0; for(long i=1;i flag=0; for(long j=n-1;j>=i;j--) {