数据结构内部排序比较课案

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. 函数如下，代码详见文件“排序比较 int Create_Sq(SqList / 定义一个数组 int lengt

3、h = sizeof(array)/sizeof(array0);/ 得到数组的长度 int min, k=0, s=0, i=0, j=0;/k 保存临时结果， s，i ，j 为循环变量 /选择排序开始 for(i=0;ilength;i+) min=i; for(j=i+1;jarrayj) min=j; if(min!=i) k=arrayi; arrayi=arrayj; arrayj=k; /选择排序结束，输出显示排序的结果 for(s=0; slength; s+) printf(%d n,arrays); return 0; /*二.冒泡排序 算法基本原理： 对尚未排序的各元素从

4、头到尾依次比较相邻的两个元素是否逆序(与欲排顺序相反) ， 若逆序就交换这两元素， 经过第一轮比较排序后便可把最大 (或最小)的元素排好， 然 后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。 算法实现： */ #include /冒泡排序 ,开始的时候两个数进行比较， 大的向后小的向前， 第一次比较很容易的就把 最大的一个数字放到了最后小的呢， 继续向前， 第二次当然也找到了第二个大的， 放到 倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让 k=j 保存最后的那个 数的下标，这样 k后面的数都是排序好的了 ,这个排序是稳定的，时间复杂度是 N 平方 int mai

5、n() int array10 = 1,2,11,22,33,4,23,234,4,6; int length = sizeof(array)/sizeof(array0); int k=0, s=0, i=0, j=0, m=0; /冒泡排序开始 for(i = length-1;i0;i=k) for(j=0, k=0;jarrayj+1)/ 把比较出来大的数据向后移动 m=arrayj; arrayj=arrayj+1; arrayj+1=m; k=j; /冒泡排序结束，输出显示排序的结果 for(s=0; slength; s+) printf(%d n,arrays); return

6、 0; /*三.快速排序 算法基本原理： 快速排序( Quicksort)是对冒泡排序的一种改进。由 C. A. R. Hoare在 1962年提出。它 的基本思想是： 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有 数据都比另外一部分的所有数据都要小， 然后再按此方法对这两部分数据分别进行快速 排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 算法实现： */ #include /快速排序开始，使用递归方法，取其中一个数(任意基本上都是以第一个为准) ，先 从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大， 则交换之，再到前面比较，

7、如果前面的比这个数小交换之再和后面的比较， 第一趟下来 比它小的就在前面了， 比它大的就在后面喽， 然后再把该数组分成两部分使用递归， 直 到最后排序完成 void paixu(int array, int low, int hight) int i,j,t,m; if(lowhight) i = low; j = hight; t = arraylow; while(ij) while(it)/ 开始和后面的比较，如果后面的比他大继续，如果后面的比它 小交换之 j-; if(ij)/ 在没有越界( i 是从前面开始， j 是从后面开始)的情况下进行交换 m=arrayi; arrayi=ar

8、rayj; arrayj=m; i+;/ 让前面的向后移动一个继续比较 while(ij if(ij) 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

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

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

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

12、ngth = sizeof(array)/sizeof(array0); int i,j,t,m; /插入排序开始 for(i=1;i0) arrayj-1=arrayj; arrayj=m; j-;/ 交换完毕继续比较 /插入排序结束 for(i=0;ilength;i+) printf(%d n,arrayi); return 0; /* 五.希尔排序 希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性， 提高了 效率。希尔排序的时间复杂度为 O(N*(logN)2) ， 没有快速排序算法快 O(N*(logN) ， 因此中等大小规模表现良好，对规模非常大的数据排序不是

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

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