C语言内排序法实验报告.doc

数据结构一：排序方法比较1、冒泡排序属于稳定排序，是一种借助“交换”进行排序的方法。首先要将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录与第三个记录的关键字，以此类推，直至第n-1个记录与第n个记录的关键字进行比较为止，这一过程称为第一趟冒泡排序，其结果使得关键字最大的记录被安置在最后一个记录的位置上；然后进行第二趟冒泡排序，对前N-1个记录进行同样操作；以此类推，直到在一趟排序过程中没有进行过交换记录的操作为止。2、直接插入排序属于稳定的排序，每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟将待比较的数值与它的前一个数值进行比较，当前一数值比待比较数值大的情况下继续循环比较，依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程，结束该次循环。3、快速排序属于不稳定排序，是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为R.s,R.s+1,.,R.t,首先任意选取一个记录，然后按下述原则从新排序记录：将关键字较他小的记录都安置在他的位置之前，将所有关键字较他大的记录都安置在他的位置后面。由此可以该“枢轴”记录最后所落的位置i作为分界线，将序列Rs,Rs+1.Rt分割成两个子序列Rs,Rs+1.Ri-1和Ri+1Rt，这个过程称作一趟快速排序。一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向数组第一个数据和最后一个数据，将枢轴记录暂存在R0的位置上排序过程中只作Rlow或Rhigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。4、简单选择排序属于不稳定排序，基本思想是，每一趟在n-i+1（i=1，2，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。5、希尔排序属于不稳定排序，也是一种属插入排序类，它的基本思想是：先将整个待排记录序列分割称为若干个子序列分别进行直接插入排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的一个特点是：子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。6、二叉树排序属于不稳定排序，它的基本思想是，先将初始文件R1.n建成一个大根堆，此堆为初始的无序区，再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key；由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆，然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n- 2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。输入待排序列Rn+1选择排序类型sortSort直接插入冒泡排序快速排序简单选择希尔排序输出结果结束二叉树排序开始二：程序流程图：三：实验总结：本实验综合了多种内排序方法，深入了解了其算法，并将6种内排序方法综合起来做了比较，对于这6种算法也更加了解，知道各自有何不同，各自适合哪种情况，虽然本次实验比较和程序段有很多都