数据结构内部排序比较

1、数据结构实训报告实验名称：数据结构题目：内部排序比较专业： 班级： 姓名： 学号： 实验日期：一、实验目的：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。三、实验内容1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种；2 、待排序的元素的关键字为整数；3 、比较的指标为有关键字参加的比较次数和关键

2、字的移动次数(关键字交换以3次计)。4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。5、最后要对结果作简单的分析。6、测试数据：用伪随机数产生程序产生。四、实验编程结果或过程：1. 数据定义typedef struct KeyType key;RedType;typedef struct RedType rMAXSIZE+1;int length;SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)/冒泡排序void In

3、sertSort(SqList &L)/插入排序 void SelectSort(SqList &L) /简单选择排序int Partition(SqList &L,int low,int high)void QSort(SqList &L,int low,int high)/递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)/希尔排序 void ShellSort(SqList &L,int dlta )3. 运行测试结果，运行结果无误，如下图语速

4、个数为20元素个数为100错误调试 无。影响排序的因素：1、待排序的记录数目n 的大小。2、记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。3、关键字的结构及其分布情况。4、对排序稳定性的要求五、实验总结：（1）实验中的存在问题和提高1、存在问题：程序有待增强。2、提高：界面处理简洁。（2）收获与体会：1、随机数的生成；2、排序的算法的比较次数与移动次数的计算3、各种排序的算法附录 源程序/*一.选择排序算法：算法基本原理：一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置mi

5、n，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。算法实现：*/#include <stdio.h>/选择排序，如果第一个数字小于后面的则向后移动，依次类推/该排序时不稳定的，时间复杂度是N平方int main()int array10 = 112,4,2,3,5,33,6,7,8,9;/定义一个数组int length = sizeof(array)/sizeof(array0);/得到数组的长度int min, k=0, s=0, i=0, j=0;/k保存临时结果，s，i，j为循环变量/选择排序开始for(i=0;i<length;i+) mi

6、n=i; for(j=i+1;j<length;j+) if(arrayi>arrayj) min=j; if(min!=i) k=arrayi; arrayi=arrayj; arrayj=k; /选择排序结束，输出显示排序的结果for(s=0; s<length; s+)printf("%d n",arrays);return 0; /*二.冒泡排序算法基本原理：对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较

7、，就得到了你所要的顺序。算法实现：*/#include <stdio.h>/冒泡排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方int main()int array10 = 1,2,11,22,33,4,23,234,4,6;int length = sizeof(array)/sizeof(array0);int k=0, s=

8、0, i=0, j=0, m=0;/冒泡排序开始for(i = length-1;i>0;i=k)for(j=0, k=0;j<i;j+)if(arrayj>arrayj+1)/把比较出来大的数据向后移动m=arrayj;arrayj=arrayj+1;arrayj+1=m;k=j;/冒泡排序结束，输出显示排序的结果for(s=0; s<length; s+)printf("%d n",arrays);return 0;/*三.快速排序算法基本原理：快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。

9、它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。算法实现：*/#include <stdio.h>/快速排序开始，使用递归方法，取其中一个数（任意基本上都是以第一个为准），先从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大，则交换之，再到前面比较，如果前面的比这个数小交换之再和后面的比较，第一趟下来比它小的就在前面了，比它大的就在后面喽，然后再把该数组分成两部分使用递归，直到最后排序完成vo

10、id paixu(int array, int low, int hight)int i,j,t,m;if(low<hight)i = low;j = hight;t = arraylow;while(i<j)while(i<j && arrayj>t)/开始和后面的比较，如果后面的比他大继续，如果后面的比它小交换之j-;if(i<j)/在没有越界（i是从前面开始，j是从后面开始）的情况下进行交换m=arrayi;arrayi=arrayj;arrayj=m;i+;/让前面的向后移动一个继续比较while(i<j && arr

11、ayi<=t)/和前面的比较，如果前面的小于等于该关键数据继续，如果大于交换之i+;if(i<j)m=arrayj;arrayj=arrayi;arrayi=m;j-;arrayi=t;/第一次比较结束，把i放到中间的位置，也即在i前面都比i小，在i后面都比i大paixu(array, low, i-1);/前面部分实现递归paixu(array, i+1, hight);/后面部分实现递归int main()int s=0;int array = 10,22,3,21,45,67,2,11,110,453;int length = sizeof(array)/sizeof(arr

12、ay0);paixu(array,s,length-1);for(s=0;s<length;s+)printf("%d n",arrays);return 0; /*四.插入排序概述：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为()。是稳定的排序方法。插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个

13、数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。包括：直接插入排序，折半插入排序，链表插入排序，Shell排序算法基本原理：假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a1k是局部有序的,保证了插入过程的正确性.算法描述：一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：1. 从第一个元素开始，该元素可以认为已经被排序2. 取出下一个元素，在已

14、经排序的元素序列中从后向前扫描3. 如果该元素（已排序）大于新元素，将该元素移到下一位置4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置5. 将新元素插入到该位置中6. 重复步骤2如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 算法实现：*/#include <stdio.h>int main()int array = 9,43,567,1,45,23,123,54,234,987;int length = sizeof(array)/sizeof(array0);int i,j,t,

15、m;/插入排序开始for(i=1;i<length;i+)/默认下标为0的已经是排序好的，所以从1开始t = arrayi;j=i;while(j>0)&&(arrayj-1>t)/如果前面的数比它大交换之m=arrayj-1;arrayj-1=arrayj;arrayj=m;j-;/交换完毕继续比较/插入排序结束for(i=0;i<length;i+)printf("%d n",arrayi);return 0; /*五.希尔排序希尔排序是基于插入排序的一种算法，在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为

16、 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN)，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当N值减小时每

17、一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。 在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。希尔排序是不稳定的。 算法实现：*/#include <stdio.h>int main()int array = 1,445,754,77,35,123,754,876,54,3;int length = sizeof