数据结构实验报告实验4

北京邮电大学信息与通信工程学院第3页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验四排序（题目1）学生姓名：班级：班内序号：学号：日期：2013年12月19日1．实验要求实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对2的结果进行分析，验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构程序采用的存储机构是顺序存储，如下图所示：a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]2.2关键算法分析2.2.1插入排序插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述过程如下：①将待插入纪录赋值给哨兵r[0]：r[0]=r[i];②从后向前进行顺序查找：for(j=i-1;r[0]<r[j];j--); ③元素后插：r[j+1]=r[j];④插入记录：r[j+1]=r[j];性能分析：原序列正序时直接插入排序达到最好的时间性能，比较次数为n-1，移动次数为0。原序列逆序时直接插入排序达到最差时间性能，比较次数为，移动次数为。 直接插入排序的平均时间复杂度为，空间复杂度为。 直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。2.2.2希尔排序 希尔排序的基本方法是将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。希尔排序的整个过程如下：for(intd=n/2;d>=1;d=d/2)//以d为增量//在子序列中进行插入排序 { for(inti=d+1;i<=n;i++)//一趟希尔排序 { if(r[i]<r[i-d]) { r[0]=r[i]; for(intj=i-d;j>0&&r[0]<r[j];j=j-d)//每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序 r[j+d]=r[j]; r[j+d]=r[0]; } }}性能分析：希尔排序的时间复杂度在和之间，空间复杂度为，是一种不稳定的排序算法。2.2.3冒泡排序冒泡排序的基本思想是，两两比较相邻的元素，如果反序，则交换位置，知道没有反序的元素为止。具体描述如下：//外循环：总共需要遍历的趟数for(inti=1;i<n;i++) {//内循环：每一趟需要比较的次数 for(intj=1;j<=n-i;j++) { if(r[j]>r[j+1])//相邻元素比较 { r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0]; //若逆序，则交换 } } }性能分析：原序列正序时冒泡排序达到最好的时间性能，比较次数为n-1，移动次数为0。原序列逆序时达到最差时间性能，比较次数为，移动次数为。平均时间复杂度为，空间复杂度为。冒泡排序是一种稳定的排序算法。2.2.4快速排序 快速排序是冒泡排序的改进算法，快速排序元素的比较和移动是从两端向中间进行的，因而元素移动的距离较远。快速排序的基本思想是，在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程直到整个序列有序。经过优化改进的快速排序算法如下：//一趟快速排序intPartion(intr[],intfirst,intend){ inti=first;intj=end; intpivot=r[i];//选取基准元素 while(i<j) { while((i<j)&&(r[j]>=pivot))//右侧扫描 { j--; } r[i]=r[j]; while((i<j)&&(r[i]<=pivot))//左侧扫描 { i++; } r[j]=r[i]; } r[i]=pivot; returni;}//快速排序voidQSort(intr[],inti,intj){//递归直到序列有序 if(i<j) { intpivotloc=Partion(r,i,j); QSort(r,i,pivotloc-1); QSort(r,pivotloc+1,j); }} 性能分析：快速排序的时间复杂度为，栈的深度为。快速排序是一种不稳定的排序方法。2.2.5简单选择排序 简单选择排序的基本思想是：第1趟，在待排序纪录r[1…n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2…n]中选出最小的记录，将它与r[2]交换……以此类推，第i趟将待排序记录r[i…n]中选出关键码最小的记录，与r[i]交换，使有序序列不断增长直到全部排序完毕。第i趟排序的过程如下：①假设index是最小的：intindex=i;②查找最小的记录：for(intj=i+1;j<=n;j++){if(r[j]<r[index])index=j;}③若第一个就是最小元素，则不用交换，否则交换，r[0]为临时空间：if(index!=i){r[0]=r[i];r[i]=r[index];r[index]=r[0];}性能分析：简单选择排序是移动次数最少的算法，当原序列为正序时，比较次数为，移动次数为0；当原始序列为逆序时，比较次数为，移动次数为；平均情况下的时间复杂度为，空间复杂度为。简单选择排序是不稳定的。2.2.6堆排序堆排序采用堆的存储结构，即将数组r[]存在一个二叉树中，根节点存放在r[1]，假设某结点存放在r[i]，则其左孩子存放在r[2i]，右孩子存放在r[2i+1]，非根结点r[i]的双亲结点存放在r[n/2]。每个结点的值都不大于其左右孩子结点的值的堆叫做小根堆，大根堆同里定义。采用小根堆存储的堆排序的基本思想为小根堆的筛选过程，即：总是将根结点与左右孩子结点进行比较，若不满足小根堆条件，则将根结点与较小的结点交换，一直到叶子结点，或所有子树均为小根堆为止。小根堆的筛选算法如下：voidSift(intr[],intk,intm)//m为编号最大的叶子结点的编号{ inti=k,j=2*i;//i是要筛选的结点，j是i的左孩子 while(j<=m) { if(j<m&&r[j]>r[j+1])//j是左右孩子中较小者 j++; if(r[i]<r[j])break;//符合小根堆的条件，结束 else { r[0]=r[i]; r[i]=r[j]; r[j]=r[0]; i=j;j=2*i; } }}堆排序的具体过程为：①将待排序的元素构造成一个堆；②输出堆顶元素；③将堆中最后一个元素移至堆顶，并将剩余元素调整成堆。反复执行②和③直到堆中只有一个元素，代码如下：voidHeapSort(intr[],intn){ for(inti=n/2;i>=1;i--)//建堆 Sift(r,i,n); for(inti=1;i<n;i++)//输出堆顶元素，重新建堆 { r[0]=r[1]; r[1]=r[n-i+1]; r[n-i+1]=r[0]; Sift(r,1,n-i); }}使用小根堆的算法时，排序结束后从r[1]到r[n]是逆序的。性能分析：堆排序可初始建堆的时间复杂度为，第i次建堆的时间复杂度为，一共n-i次输出堆顶元素，总的时间复杂度为。堆排序是不稳定的排序算法。2.3性能比较排序方法平均时间复杂度辅助空间稳定性直接插入排序稳定希尔排序~不稳定冒泡排序稳定快速排序~不稳定简单选择排序不稳定堆排序稳定3.程序运行结果测试主函数流程：开开始构造正序、逆序、随机序列构造正序、逆序、随机序列对正序序列使用七种排序方法对逆序序列使用七种排序方法对随机序列使用七种排序方法结束结束测试条件：编译环境为MicrosoftVisualStudio2010Ultimate